Двійковий пошук

Знаходить значення у відсортованому масиві: дивиться в середину й відкидає половину, де його бути не може. Кожне порівняння вдвічі зменшує те, що лишилося.

найкраща Ω(1)
середня Θ(log n)
найгірша O(log n)
пам'ять O(1)

Що це означає?

Відсортовано: за зростанням. Двійковому пошуку це потрібно; на невідсортованих даних він помиляється.
Ділення навпіл: кожне порівняння відкидає половину залишку — ту, де цілі бути не може.
log₂ n: скільки разів n можна поділити навпіл, доки не лишиться 1. Для 64 значень це 6, тобто не більше 7 порівнянь.

середина (mid)
знайдено
відкинуто
ціль

0 / 14 кроків

Кожна середина, яку може вибрати пошук; прогін — один шлях донизу. Рівнів: 5 = ⌈log₂(24 + 1)⌉ — стільки порівнянь може знадобитися в найгіршому разі.

Швидкість 8 кроків/с

Пробіл: відтворення або пауза. Стрілки ліворуч і праворуч: крок. Home і End: на початок або в кінець.

Спробуйте: Виберіть ціль, якої немає в масиві. Пошук однаково завершиться не більше ніж за ⌈log₂(n + 1)⌉ порівнянь, коли lo обжене hi.

Як це працює

Двійковий пошук тримає дві мітки, lo і hi, навколо тієї частини масиву, де ціль ще може бути. Він дивиться на значення в середині: якщо це ціль — готово; якщо воно менше, ціль може бути лише праворуч, і lo переходить за середину; якщо більше, hi переходить перед нею. Кожен крок ділить залишок навпіл: для 64 значень вистачає 7 порівнянь, для мільйона — 20. Коли lo обганяє hi, нічого не лишається: значення в масиві немає.

Коли варто використовувати

Двійковий пошук підходить, коли дані відсортовані й можна перейти до будь-якої позиції: слово у відсортованому списку, версія в історії релізів, git bisect, місце вставки у відсортований масив. На невідсортованих даних він помиляється, а сортувати заздалегідь вигідно, лише якщо шукати багато разів.