Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння.
Двійковий пошук виконується за логарифмічний час у найгіршому випадку, виконуючи порівнянь, де — кількість елементів у масиві. Він є швидшим за лінійний пошук, за винятком невеликих масивів. Однак, щоб можна було застосувати двійковий пошук, масив повинен бути спочатку відсортованим. Існують спеціалізовані структури даних, призначені для швидкого пошуку, такі як хеш-таблиці, які дозволяють здійснювати пошук ефективніше за двійковий пошук. Проте, двійковий пошук може бути використаний для вирішення ширшого кола задач, наприклад, для пошуку наступного найменшого або наступного найбільшого елемента в масиві відносно заданого елемента, навіть якщо він відсутній в масиві.
Алгоритм Двійковий пошук працює на впорядкованих масивах. Він починається з порівняння шуканого елемента з елементом в середині масиву. Якщо вони рівні, то повертається позиція середнього елемента в масиві. Якщо шуканий елемент виявляється меншим, то пошук продовжується в лівій половині масиву. Якщо шуканий елемент виявляється більшим, то пошук продовжується у правій половині масиву. Таким чином, алгоритм виключає ту половину масиву, в якій немає шуканого елемента.
Процедура Неха задано масив з елементів впорядкованих таким чином, що та шуканий елемент Наступна процедура реалізовує двійковий пошук для знаходження індексу елемента в Встановити значення рівним та рівним Якщо то пошук завершується як невдалий. Встановити позицію середнього елемента де — позначення підлоги числа. Якщо , то встановити значення рівним та перейти до кроку 2. Якщо , то встановити значення рівним та перейти до кроку 2. Тепер , тому пошук завершено; повернути
Ця ітеративна процедура відстежує межі пошуку за допомогою двох змінних та . Вона може бути виражена в псевдокоді, де імена та типи змінних залишаються такими ж, як і вище, floor — це підлога числа, а unsuccessful позначає специфічне значення, яке повідомляє про невдачу пошуку, таким чином:
function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := L + floor((R - L) / 2) if A[m] < T then L := m + 1 else if A[m] > T then R := m − 1 else: return m return unsuccessful
Альтернативна процедура У наведеній вище процедурі алгоритм перевіряє, чи середній елемент дорівнює шуканому елементу у кожній ітерації. Деякі реалізації пропускають цю перевірку. Алгоритм виконує цю перевірку тільки тоді, коли залишається один елемент (коли ). Це прискорює цикл порівнянь, бо з нього виключається одне порівняння, а його кількість ітерацій в середньому збільшується на одиницю. Процедура описана на с. 214 (§ 43) під назвою «Program for Binary Search».
опублікував першу реалізацію, в якій ця перевірка була виключена, в 1962 році. Встановити значення рівним та рівним Поки Встановити позицію середнього елемента де — позначення стелі числа. Якщо то встановити значення рівним Інакше, ; встановити значення рівним Тепер , пошук завершено. Якщо , то повернути Інакше, пошук завершується як невдалий.
Псевдокод цієї версії, де ceil — це стеля числа, виглядає таким чином: function binary_search_alternative(A, n, T) is L := 0 R := n − 1 while L != R do m := L + ceil((R - L) / 2) if A[m] > T then R := m − 1 else: L := m if A[L] = T then return L return unsuccessful
Однакові елементи Процедура може повернути будь-який індекс, елемент якого дорівнює шуканому значенню, якщо в масиві є однакові елементи. Наприклад, при пошуку елемента 4 у масиві , алгоритм може повернути або 4-й (індекс 3), або 5-й (індекс 4) елемент. У цьому випадку перша процедура поверне 4-й елемент (індекс 3). Вона не завжди повертає перший дублікат (для масиву вона все одно поверне 4-й елемент). Однак іноді необхідно знайти крайню ліву або крайню праву позицію шуканого елемента, який повторюється в масиві. У наведеному вище прикладі 4-й елемент є крайнім лівим елементом значення 4, а 5-й елемент — крайнім правим елементом того ж значення. Альтернативна процедура, наведена вище, завжди повертатиме індекс крайнього правого елемента, якщо такий елемент існує.
Процедура пошуку крайнього лівого елемента Щоб знайти крайній лівий елемент, можна скористатися такою процедурою: Встановити значення рівним та рівним Поки Встановити позицію середнього елемента Якщо то встановити значення рівним Інакше, ; встановити значення рівним Повернути Якщо та то є крайнім лівим елементом, що дорівнює Якщо не належить масиву, то — це кількість елементів у масиві, які менші за
Псевдокод цієї версії виглядає таким чином: function binary_search_leftmost(A, n, T): L := 0 R := n while L < R: m := L + floor((R - L) / 2) if A[m] < T: L := m + 1 else: R := m return L
Процедура пошуку крайнього правого елемента Щоб знайти крайній правий елемент, можна скористатися такою процедурою: Встановити значення рівним та рівним Поки Встановити позицію середнього елемента Якщо то встановити значення рівним Інакше, ; встановити значення рівним Повернути Якщо та то є крайнім правим елементом, що дорівнює Якщо не належить масиву, то — це кількість елементів у масиві, які більші за
Псевдокод цієї версії виглядає таким чином: function binary_search_rightmost(A, n, T): L := 0 R := n while L < R: m := L + floor((R - L) / 2) if A[m] > T: R := m else: L := m + 1 return R - 1
Наближені елементи
Початкова процедура шукає лише точні збіги, визначаючи положення шуканого елемента. Оскільки двійковий пошук працює з впорядкованими масивами, то його можна розширити для пошуку наближених збігів. Наприклад, двійковий пошук можна використовувати для знаходження рангу (кількість менших елементів) шуканого елемента, попередника (наступний за спаданням елемент), наступника (наступний за зростанням елемент) та найближчого сусіда. , що визначають кількість елементів між двома значеннями, можна виконувати за допомогою двох знаходжень рангу.
Визначити ранг шуканого елемента можна за допомогою процедури пошуку крайнього лівого елемента. Вона повертає кількість елементів, менших за шуканий елемент. Знайти попередника можна за допомогою рангу. Якщо ранг шуканого елемента дорівнює то його попередник має індекс Знайти наступника можна за допомогою процедури пошуку крайнього правого елемента. Якщо результатом її виконання для шуканого елемента є то наступник цього елемента має індекс Як тільки ранги двох елементів відомі, кількість елементів масиву, більших або рівних меншому з них та менших за більшого з них, дорівнює різниці їх рангів. Ця кількість може бути збільшена або зменшена, залежно від того, чи межі діапазону слід вважати його частиною і чи сам масив містить крайні елементи діапазону.
Швидкодія
З погляду кількості порівнянь, ефективність двійкового пошуку можна проаналізувати, переглянувши його виконання на двійковому дереві. Корінь цього дерева містить середній елемент масиву. Середній елемент лівої половини масиву є лівою дитиною кореня, а середній елемент правої половини є правою дитиною кореня. Решта дерева побудована аналогічним чином. Починаючи з кореня, ліве або праве піддерево обходиться залежно від того, чи шуканий елемент менший або більший за елемент у розглянутому вузлі.
У найгіршому випадку двійковий пошук виконує ітерацій циклу, де — це двійковий логарифм. Це пов'язано з тим, що найгірший випадок настає тоді, коли пошук досягає листя дерева, а дерево будь-якого двійкового пошуку завжди має висоту Найгірший випадок також може настати, коли шуканий елемент відсутній у масиві. Це завжди так, коли на одиницю менший за степінь двійки. В іншому випадку він може виконати ітерацій та завершитися невдало, тобто закінчитися на другому за глибиною рівні двійкового дерева.
Коли шуканий елемент знаходиться в масиві, то, припускаючи, що кожен його елемент має однакову ймовірність бути знайденим, двійковий пошук виконує в середньому ітерацій. Це приблизно дорівнює ітерацій. Коли шуканий елемент відсутній у масиві, то, припускаючи, що кожен елемент масиву та шуканий елемент мають однакову ймовірність бути знайденими, двійковий пошук виконує в середньому ітерацій. У найкращому випадку, коли шуканий елемент знаходиться по середині масиву, його позиція повертається після однієї ітерації циклу алгоритму.
З погляду ітерацій, жоден алгоритм пошуку, який працює тільки шляхом порівняння елементів, не може продемонструвати кращу середню та найгіршу швидкодію, ніж у двійкового пошуку. Дерево порівнянь, що відповідає цьому алгоритму, має найменшу кількість рівнів, оскільки кожен рівень вище найнижчого рівня дерева повністю заповнений. Інші алгоритми пошуку, засновані на порівняннях, хоч можуть іноді працювати швидше, але їхня середня швидкодія гірша, ніж у двійкового пошуку. Розділяючи масив навпіл, двійковий пошук гарантує, що розміри обох підмасивів будуть подібними настільки, наскільки це можливо.
Швидкодія альтернативної процедури Кожна ітерація першої процедури двійкового пошуку, визначеної вище, виконує одне або два порівняння, перевіряючи, чи середній елемент дорівнює шуканому. Припускаючи, що кожен елемент має однакову ймовірність бути знайденим, вона виконує в середньому 1,5 порівняння. Альтернативний алгоритм перевіряє, чи середній елемент дорівнює шуканому в кінці пошуку. В середньому у ній відсутня половина порівнянь з усіх ітерацій. Це трохи скорочує час, що витрачається на кожну ітерацію на більшості комп'ютерів. Однак такий пошук займає максимальну кількість ітерацій, в середньому на одну ітерацію більше ніж в оригінальному алгоритмі. Оскільки цикл порівнянь виконується тільки разів у найгіршому випадку, невелике підвищення ефективності ітерації не компенсує додаткову ітерацію для всіх, крім дуже великих .
Порівняння з іншими методами Впорядковані масиви з двійковим пошуком є неефективним рішенням, коли операції вставки та видалення, які виконуються в середньому за ітерацій, чергуються з операціями пошуку. Крім того, вони можуть ускладнювати використання пам'яті, особливо коли елементи часто вставляються в масив. Існують інші структури даних, які підтримують набагато ефективніше вставлення та видалення. Двійковий пошук може використовуватися для знаходження елемента, який точного збігається із шуканим, та визначення його входження до множини. Також є структури даних, які підтримують швидше знаходження точного збігу та визначення входження до множини. Однак, на відміну від багатьох інших методів пошуку, двійковий пошук може використовуватися для ефективного знаходження наближеного збігу, зазвичай визначаючи такі збіги за час незалежно від типу самих значень масиву.
Лінійний пошук Лінійний пошук — це алгоритм, який послідовно перевіряє кожен елемент масиву, поки не знайде шуканий елемент. Його можна виконувати на зв'язаному списку, що дозволяє швидше вставляти та видаляти елементи, ніж у масиві. Двійковий пошук швидший за лінійний пошук на впорядкованих масивах, за винятком випадків, коли вони мають малі розміри.
Дерева
Двійкове дерево пошуку — це двійкове дерево, яке базується на принципі двійкового пошуку. Воно будується таким чином, що кожен його елемент можна знайти за допомогою алгоритму, схожого на двійковий пошук, що займає в середньому логарифмічний час. У двійковому дереві пошуку вставка та видалення також виконуються в середньому за логарифмічний час. Це швидше, ніж лінійний час вставки та видалення у відсортованому масиві. Двійкове дерево має можливість виконувати всі операції, які можливі для відсортованого масиву, включаючи запит за діапазоном та пошук наближених елементів.