Часова складність з Двійковий пошук є O(log n) , де п кількість елементів у масиві. Він ділить масив навпіл на кожному кроці. Космічна складність є О(1) оскільки він постійно займає додатковий простір.

Приклад алгоритму бінарного пошуку

Часові та просторові складності алгоритму бінарного пошуку згадуються нижче.

Часова складність Алгоритм бінарного пошуку :

Найкращий випадок складності часу бінарного алгоритму пошуку: О(1)

Найкращий випадок, коли елемент знаходиться в середньому індексі масиву. Щоб знайти цільовий елемент, потрібно лише одне порівняння. Отже, найкраща складність випадку О(1) .

Середня складність випадку алгоритму бінарного пошуку: O(log N)

Розглянемо масив обр[] довжини Н і елемент X бути знайденим. Може бути два випадки:

• Випадок 1: Елемент присутній у масиві
• Case2: Елемент відсутній у масиві.

Є Н Випадок1 і 1 Випадок2. Отже, загальна кількість випадків = N+1 . Тепер зауважте наступне:

• Елемент з індексом N/2 можна знайти в 1 порівняння
• Елементи з індексами N/4 і 3N/4 можна знайти в 2 порівняння.
• Елементи з індексами N/8, 3N/8, 5N/8 і 7N/8 можна знайти в 3 порівняння тощо.

Виходячи з цього можна зробити висновок, що елементи, які потребують:

• 1 порівняння = 1
• 2 порівняння = 2
• 3 порівняння = 4
• x порівняння = 2 ^х-1 де x належить до асортименту [1, logN] оскільки максимальні порівняння = максимальний час N можна скоротити вдвічі = максимальні порівняння для досягнення 1-го елемента = logN.

Отже, загальні порівняння
= 1*(елементи, які потребують 1 порівняння) + 2*(елементи, які потребують 2 порівнянь) + . . . + logN*(елементи, які потребують порівняння logN)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2 ^logN-1 )
= 2 ^{спокійний} * (logN – 1) + 1
= N * (logN – 1) + 1

Загальна кількість випадків = N+1 .

Тому середня складність = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Тут домінуючим членом є N*logN/(N+1), що є приблизно спокійний . Отже, середня складність справи O(logN)

Найгірша часова складність алгоритму бінарного пошуку: O(log N)

Найгірше буде, коли елемент присутній на першій позиції. Як видно в середньому випадку, порівняння, необхідне для досягнення першого елемента спокійний . Тож часова складність у гіршому випадку така O(logN) .

Складність допоміжного простору алгоритму бінарного пошуку

The складність допоміжних приміщень з Алгоритм бінарного пошуку є О(1) , що означає, що він потребує постійної кількості додаткового простору незалежно від розміру вхідного масиву. Це пояснюється тим, що двійковий пошук — це ітеративний алгоритм, який не потребує жодних додаткових структур даних або рекурсії, яка зростає зі збільшенням розміру вхідних даних. Хоча ми також можемо реалізувати бінарний пошук рекурсивно.