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

Двійковий пошук
	Візуалізація алгоритму двійкового пошуку, де 7 — шуканий елемент
Клас	Алгоритм пошуку
Структура даних	Масив
Найгірша швидкодія	O(log n)
Просторова складність у найгіршому випадку	O(1)
Оптимальний	Так

Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння.

Двійковий пошук виконується за логарифмічний час у найгіршому випадку, виконуючи $O(\log _{2}n)$ порівнянь, де $n$ — кількість елементів у масиві.^[1] Він є швидшим за лінійний пошук, за винятком невеликих масивів. Однак, щоб можна було застосувати двійковий пошук, масив повинен бути спочатку відсортованим. Існують спеціалізовані структури даних, призначені для швидкого пошуку, такі як хеш-таблиці, які дозволяють здійснювати пошук ефективніше за двійковий пошук. Проте, двійковий пошук може бути використаний для вирішення ширшого кола задач, наприклад, для пошуку наступного найменшого або наступного найбільшого елемента в масиві відносно заданого елемента, навіть якщо він відсутній в масиві.

Алгоритм

Двійковий пошук працює на впорядкованих масивах. Він починається з порівняння шуканого елемента з елементом в середині масиву. Якщо вони рівні, то повертається позиція середнього елемента в масиві. Якщо шуканий елемент виявляється меншим, то пошук продовжується в лівій половині масиву. Якщо шуканий елемент виявляється більшим, то пошук продовжується у правій половині масиву. Таким чином, алгоритм виключає ту половину масиву, в якій немає шуканого елемента.^[2]

Процедура

Неха задано масив $A$ з $n$ елементів $A_{0},A_{1},A_{2},\dots ,A_{n-1},$ впорядкованих таким чином, що $A_{0}\leqslant A_{1}\leqslant A_{2}\leqslant \cdots \leqslant A_{n-1},$ та шуканий елемент $T.$ Наступна процедура реалізовує двійковий пошук для знаходження індексу елемента $T$ в $A.$ ^[2]

Встановити значення $L$ рівним $0$ та $R$ рівним $n-1.$
Якщо $L>R,$ то пошук завершується як невдалий.
Встановити позицію середнього елемента $m=L+\left\lfloor {\frac {R-L}{2}}\right\rfloor ,$ де $\lfloor \cdot \rfloor$ — позначення підлоги числа.
Якщо $A_{m}<T$ , то встановити значення $L$ рівним $m+1$ та перейти до кроку 2.
Якщо $A_{m}>T$ , то встановити значення $R$ рівним $m-1$ та перейти до кроку 2.
Тепер $A_{m}=T$ , тому пошук завершено; повернути $m.$

Ця ітеративна процедура відстежує межі пошуку за допомогою двох змінних $L$ та $R$ . Вона може бути виражена в псевдокоді, де імена та типи змінних залишаються такими ж, як і вище, floor — це підлога числа, а unsuccessful позначає специфічне значення, яке повідомляє про невдачу пошуку, таким чином:^[2]

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

Альтернативна процедура

У наведеній вище процедурі алгоритм перевіряє, чи середній елемент $A_{m}$ дорівнює шуканому елементу $T$ у кожній ітерації. Деякі реалізації пропускають цю перевірку. Алгоритм виконує цю перевірку тільки тоді, коли залишається один елемент (коли $L=R$ ). Це прискорює цикл порівнянь, бо з нього виключається одне порівняння, а його кількість ітерацій в середньому збільшується на одиницю.^[3]

Герман Боттенбрух^[en] опублікував першу реалізацію, в якій ця перевірка була виключена, в 1962 році.^[3]^[4]

Встановити значення $L$ рівним $0$ та $R$ рівним $n-1.$
Поки $L\neq R,$ $L\neq R,$
1. Встановити позицію середнього елемента $m=L+\left\lceil {\frac {R-L}{2}}\right\rceil ,$ де $\lceil \cdot \rceil$ — позначення стелі числа.
2. Якщо $A_{m}>T,$ то встановити значення $R$ рівним $m-1.$
3. Інакше, $A_{m}\leqslant T$ ; встановити значення $L$ рівним $m.$
Тепер $L=R$ , пошук завершено. Якщо $A_{L}=T$ , то повернути $L.$ Інакше, пошук завершується як невдалий.

Псевдокод цієї версії, де 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 у масиві $[1, 2, 3, 4, 4, 5, 6, 7]$ , алгоритм може повернути або 4-й (індекс 3), або 5-й (індекс 4) елемент. У цьому випадку перша процедура поверне 4-й елемент (індекс 3). Вона не завжди повертає перший дублікат (для масиву $[1, 2, 4, 4, 4, 5, 6, 7]$ вона все одно поверне 4-й елемент). Однак іноді необхідно знайти крайню ліву або крайню праву позицію шуканого елемента, який повторюється в масиві. У наведеному вище прикладі 4-й елемент є крайнім лівим елементом значення 4, а 5-й елемент — крайнім правим елементом того ж значення. Альтернативна процедура, наведена вище, завжди повертатиме індекс крайнього правого елемента, якщо такий елемент існує.^[4]

Процедура пошуку крайнього лівого елемента

Щоб знайти крайній лівий елемент, можна скористатися такою процедурою:^[5]

Встановити значення $L$ рівним $0$ та $R$ рівним $n.$
Поки $L<R,$ $L<R,$
1. Встановити позицію середнього елемента $m=L+\left\lfloor {\frac {R-L}{2}}\right\rfloor .$
2. Якщо $A_{m}<T,$ то встановити значення $L$ рівним $m+1.$
3. Інакше, $A_{m}\geqslant T$ ; встановити значення $R$ рівним $m.$
Повернути $L.$

Якщо $L<n$ та $A_{L}=T,$ то $A_{L}$ є крайнім лівим елементом, що дорівнює $T.$ Якщо $T$ не належить масиву, то $L$ — це кількість елементів у масиві, які менші за $T.$

Псевдокод цієї версії виглядає таким чином:

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

Процедура пошуку крайнього правого елемента

Щоб знайти крайній правий елемент, можна скористатися такою процедурою:^[5]

Встановити значення $L$ рівним $0$ та $R$ рівним $n.$
Поки $L<R,$ $L<R,$
1. Встановити позицію середнього елемента $m=L+\left\lfloor {\frac {R-L}{2}}\right\rfloor .$
2. Якщо $A_{m}>T,$ то встановити значення $R$ рівним $m.$
3. Інакше, $A_{m}\leqslant T$ ; встановити значення $L$ рівним $m+1.$
Повернути $R-1.$

Якщо $R>0$ та $A_{R-1}=T,$ то $A_{R-1}$ є крайнім правим елементом, що дорівнює $T.$ Якщо $T$ не належить масиву, то $n-R$ — це кількість елементів у масиві, які більші за $T.$

Псевдокод цієї версії виглядає таким чином:

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

Наближені елементи

Двійковий пошук можна застосовувати для знаходження наближених елементів. На рисунку показано ранг, попередника, наступника та найближчого сусіда для шуканого елемента $5$ , якого немає в масиві.

Початкова процедура шукає лише точні збіги, визначаючи положення шуканого елемента. Оскільки двійковий пошук працює з впорядкованими масивами, то його можна розширити для пошуку наближених збігів. Наприклад, двійковий пошук можна використовувати для знаходження рангу (кількість менших елементів) шуканого елемента, попередника (наступний за спаданням елемент), наступника (наступний за зростанням елемент) та найближчого сусіда. Запити за діапазоном^[en], що визначають кількість елементів між двома значеннями, можна виконувати за допомогою двох знаходжень рангу.^[6]

Визначити ранг шуканого елемента можна за допомогою процедури пошуку крайнього лівого елемента. Вона повертає кількість елементів, менших за шуканий елемент.^[6]
Знайти попередника можна за допомогою рангу. Якщо ранг шуканого елемента дорівнює $k,$ то його попередник має індекс $k-1.$ ^[7]
Знайти наступника можна за допомогою процедури пошуку крайнього правого елемента. Якщо результатом її виконання для шуканого елемента є $r,$ то наступник цього елемента має індекс $r+1.$ ^[7]
Як тільки ранги двох елементів відомі, кількість елементів масиву, більших або рівних меншому з них та менших за більшого з них, дорівнює різниці їх рангів. Ця кількість може бути збільшена або зменшена, залежно від того, чи межі діапазону слід вважати його частиною і чи сам масив містить крайні елементи діапазону.^[8]

Швидкодія

З погляду кількості порівнянь, ефективність двійкового пошуку можна проаналізувати, переглянувши його виконання на двійковому дереві. Корінь цього дерева містить середній елемент масиву. Середній елемент лівої половини масиву є лівою дитиною кореня, а середній елемент правої половини є правою дитиною кореня. Решта дерева побудована аналогічним чином. Починаючи з кореня, ліве або праве піддерево обходиться залежно від того, чи шуканий елемент менший або більший за елемент у розглянутому вузлі.^[1]^[9]

У найгіршому випадку двійковий пошук виконує ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ітерацій циклу, де ${\textstyle \log _{2}}$ — це двійковий логарифм. Це пов'язано з тим, що найгірший випадок настає тоді, коли пошук досягає листя дерева, а дерево будь-якого двійкового пошуку завжди має висоту ${\textstyle \lfloor \log _{2}(n)+1\rfloor .}$ Найгірший випадок також може настати, коли шуканий елемент відсутній у масиві. Це завжди так, коли $n$ на одиницю менший за степінь двійки. В іншому випадку він може виконати ${\textstyle \lfloor \log _{2}(n)\rfloor }$ ітерацій та завершитися невдало, тобто закінчитися на другому за глибиною рівні двійкового дерева.^[10]

Коли шуканий елемент знаходиться в масиві, то, припускаючи, що кожен його елемент має однакову ймовірність бути знайденим, двійковий пошук виконує в середньому $\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n$ ітерацій. Це приблизно дорівнює $\log _{2}(n)-1$ ітерацій. Коли шуканий елемент відсутній у масиві, то, припускаючи, що кожен елемент масиву та шуканий елемент мають однакову ймовірність бути знайденими, двійковий пошук виконує в середньому $\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$ ітерацій.^[11] У найкращому випадку, коли шуканий елемент знаходиться по середині масиву, його позиція повертається після однієї ітерації циклу алгоритму.^[12]

З погляду ітерацій, жоден алгоритм пошуку, який працює тільки шляхом порівняння елементів, не може продемонструвати кращу середню та найгіршу швидкодію, ніж у двійкового пошуку. Дерево порівнянь, що відповідає цьому алгоритму, має найменшу кількість рівнів, оскільки кожен рівень вище найнижчого рівня дерева повністю заповнений. Інші алгоритми пошуку, засновані на порівняннях, хоч можуть іноді працювати швидше, але їхня середня швидкодія гірша, ніж у двійкового пошуку. Розділяючи масив навпіл, двійковий пошук гарантує, що розміри обох підмасивів будуть подібними настільки, наскільки це можливо.^[10]

Швидкодія альтернативної процедури

Кожна ітерація першої процедури двійкового пошуку, визначеної вище, виконує одне або два порівняння, перевіряючи, чи середній елемент дорівнює шуканому. Припускаючи, що кожен елемент має однакову ймовірність бути знайденим, вона виконує в середньому 1,5 порівняння. Альтернативний алгоритм перевіряє, чи середній елемент дорівнює шуканому в кінці пошуку. В середньому у ній відсутня половина порівнянь з усіх ітерацій. Це трохи скорочує час, що витрачається на кожну ітерацію на більшості комп'ютерів. Однак такий пошук займає максимальну кількість ітерацій, в середньому на одну ітерацію більше ніж в оригінальному алгоритмі. Оскільки цикл порівнянь виконується тільки ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ разів у найгіршому випадку, невелике підвищення ефективності ітерації не компенсує додаткову ітерацію для всіх, крім дуже великих $n$ .^[13]^[14]

Порівняння з іншими методами

Впорядковані масиви з двійковим пошуком є неефективним рішенням, коли операції вставки та видалення, які виконуються в середньому за $O(n)$ ітерацій, чергуються з операціями пошуку. Крім того, вони можуть ускладнювати використання пам'яті, особливо коли елементи часто вставляються в масив.^[15] Існують інші структури даних, які підтримують набагато ефективніше вставлення та видалення. Двійковий пошук може використовуватися для знаходження елемента, який точного збігається із шуканим, та визначення його входження до множини. Також є структури даних, які підтримують швидше знаходження точного збігу та визначення входження до множини. Однак, на відміну від багатьох інших методів пошуку, двійковий пошук може використовуватися для ефективного знаходження наближеного збігу, зазвичай визначаючи такі збіги за час ${\textstyle O(\log _{2}n)}$ незалежно від типу самих значень масиву.^[16]

Лінійний пошук

Лінійний пошук — це алгоритм, який послідовно перевіряє кожен елемент масиву, поки не знайде шуканий елемент. Його можна виконувати на зв'язаному списку, що дозволяє швидше вставляти та видаляти елементи, ніж у масиві. Двійковий пошук швидший за лінійний пошук на впорядкованих масивах, за винятком випадків, коли вони мають малі розміри.^[17]^[18]

Дерева

Двійкове дерево пошуку — це двійкове дерево, яке базується на принципі двійкового пошуку. Воно будується таким чином, що кожен його елемент можна знайти за допомогою алгоритму, схожого на двійковий пошук, що займає в середньому логарифмічний час. У двійковому дереві пошуку вставка та видалення також виконуються в середньому за логарифмічний час. Це швидше, ніж лінійний час вставки та видалення у відсортованому масиві. Двійкове дерево має можливість виконувати всі операції, які можливі для відсортованого масиву, включаючи запит за діапазоном та пошук наближених елементів.^[16]^[19]

Однак двійковий пошук зазвичай ефективніший для пошуку, оскільки двійкове пошукове дерево, скоріш за все, буде мало збалансованим, що призведе до дещо гіршої швидкодії. Це стосується навіть збалансованого двійкового пошукового дерева, яке збалансовує свої власні вузли, бо у нього рідко утворюється найменша можлива кількість рівнів. За винятком збалансованого двійкового пошукового дерева, дерево може бути сильно незбалансованим з невеликою кількістю внутрішніх вузлів з двома дітьми, що призведе до того, що середній та найгірший часи пошуку наближатимуться до $n$ порівнянь. Також двійкове дерево пошуку займає більше місця, ніж впорядкований масив з такою самою кількістю елементів.^[20]

Хешування

Пошук у хеш-таблиці, структури даних, у якій ключі відображаються на значення за допомогою хеш-функції, як правило, є швидшим за двійковий пошук у впорядкованому масиві.^[21] Більшість реалізацій хеш-таблиці виконуються в середньому за амортизований сталий час.^[22] Однак хешування не придатне для знаходження наближених збігів, таких як попередник, наступник та найближчий сусід, бо єдина інформація, що надається при невдалому пошуку, полягає в тому, що шуканого елемента немає у хеш-таблиці.^[23]

Визначення належності до множини

Визначення належності до множини — це задача, пов'язана з пошуком. Будь-який алгоритм, що виконує пошук також може використовуватися для розв'язання цієї задачі. Існують методи, які оптимальніше підходять для визначення належності до множини, ніж двійковий пошук. Наприклад, бітова мапа корисна тоді, коли діапазон ключів обмежений. Вона компактно зберігає набір бітів, кожен з яких представляє окремий ключ у діапазоні ключів. Стандартні операції над бітовою мапою працюють швидко, виконуючись за сталий час.^[24]

Для отримання наближених значень можна використовувати фільтр Блума, ймовірнісної структури даних, заснованої на хешуванні, яка зберігає набір ключів, кодуючи їх за допомогою бітової мапи та декількох хеш-функцій. Фільтр Блума в більшості випадків ефективніше використовує пам'ять, ніж бітова мапа, і не набагато повільніший: з $k$ хеш-функціями визначення належності вимагає ${\textstyle O(k)}$ часу. Однак він схильний до хибно позитивних результатів.^[25]

Інші структури даних

Існують структури даних з відповідними алгоритмами, які в деяких випадках працюють ефективніше, ніж впорядкований масив з двійковим пошуком, як для пошуку, так і для інших операцій, доступних для впорядкованих масивів. Наприклад, пошук та знаходження наближених елементів можуть виконуватися ефективніше на спеціалізованих структурах даних, таких як дерево ван Емде Боаса, дерево злиття^[en], префіксне дерево та бітова мапа. Ці спеціалізовані структури даних використовують властивості ключів з певним атрибутом (зазвичай це ключі, що є невеликими цілими числами), і тому будуть витрачати час або пам'ять для ключів, які не мають цього атрибуту.^[16]

Варіації

Рівномірний двійковий пошук

Докладніше: Рівномірний двійковий пошук^[en]

Рівномірний двійковий пошук зберігає, замість лівої та правої меж, індекс середнього елемента та різницю індексів середнього елемента поточної ітерації та середнього елемента наступної ітерації. Для нього заздалегідь створюється таблиця пошуку, що містить такі різниці. Наприклад, у масиві $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]$ середнім елементом буде $6$ . У цьому випадку середнім елементом лівого підмасиву $[1, 2, 3, 4, 5]$ буде $3$ , а середнім елементом правого підмасиву $[7, 8, 9, 10, 11]$ — $9$ . Рівномірний двійковий пошук збереже значення $3$ , бо обидва індекси відрізняються від $6$ на одну і ту ж величину. Щоб зменшити діапазон пошуку, алгоритм додає або віднімає цю різницю від індексу середнього елемента. Рівномірний двійковий пошук може бути швидшим на комп'ютерах, де обчислення індексу середнього елемента є неефективним, наприклад, на десяткових комп'ютерах.^[26]

Експоненційний пошук

Докладніше: Експоненційний пошук^[en]

Експоненційний пошук розширює двійковий пошук на необмежені списки. Він починається з пошуку першого елемента, більшого за шуканий елемент, з індексом, який є степенем двійки. Після цього він встановлює цей індекс як праву межу і переходить до двійкового пошуку. Цей алгоритм займає ${\textstyle \lfloor \log _{2}x+1\rfloor }$ ітерацій до початку двійкового пошуку і максимум ${\textstyle \lfloor \log _{2}x\rfloor }$ ітерацій двійкового пошуку, де ${\textstyle x}$ — позиція шуканого елемента. Експоненційний пошук також працює на обмежених списках, але він стає ефективнішим за двійковий пошук лише тоді, коли шуканий елемент знаходиться близько до початку масиву.^[27]

Інтерполяційний пошук

Докладніше: Інтерполяційний алгоритм пошуку

Замість обчислення індексу середнього елемента масиву, інтерполяційний пошук оцінює положення шуканого елемента, беручи до уваги найменший та найбільший елементи в масиві, а також розмір масиву. Він спирається на припущення, що розбивати масив по середньому елементу в багатьох випадках не є найкращим способом досягати шуканого елемента. Наприклад, якщо шуканий елемент близький до найбільшого елемента в масиві, то, ймовірно, він буде розташований біля кінця масиву.^[28]

Поширеною функцією інтерполяції є лінійна інтерполяція. Якщо $A$ — масив, $L$ та $R$ — ліва і права межі відповідно, то положення шуканого елемента $T$ оцінюється приблизно як $(T - A L) / (A R - A L)$ відстані між $L$ і $R$ . Коли використовується лінійна інтерполяція, а розподіл елементів масиву є рівномірним або майже рівномірним, інтерполяційний пошук виконує в середньому ${\textstyle O(\log _{2}\log _{2}n)}$ порівнянь.^[28]^[29]

На практиці інтерполяційний пошук повільніший за двійковий пошук для невеликих масивів, бо він виконує більше обчислень на кожній ітерації. Хоч зростання його часової складності повільніше, ніж у двійкового пошуку, однак воно починає компенсувати додаткові обчислення лише для великих масивів.^[28]

Дробове каскадування

Докладніше: Дробове каскадування^[en]

Дробове каскадування — це спосіб прискорення двійкового пошуку для одного й того ж елемента в декількох впорядкованих масивах. Пошук у кожному масиві окремо вимагає часу ${\textstyle O(k\log _{2}n)}$ , де $k$ — кількість масивів. Дробове каскадування скорочує цей час до ${\textstyle O(k+\log _{2}n)}$ шляхом зберігання в кожному масиві конкретної інформації про кожен елемент і його положення в інших масивах.^[30]^[31]

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

Алгоритм двійкового пошуку із шумом (англ. Noisy binary search) підходить для випадків, коли алгоритм не може надійно порівняти елементи масиву. Для кожної пари елементів існує певна ймовірність, що алгоритм зробить неправильне порівняння. Він може знайти правильне положення шуканого елемента із заданою ймовірністю. Двійковий пошук із шумом робить щонайменше $(1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}$ порівнянь, де $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ — функція двійкової ентропії^[en], а $\tau$ — ймовірність того, що алгоритм дасть хибне положення.^[32]^[33]^[34] Задачу, яку розв'язує цей алгоритм, можна розглядати як частковий випадок гри Реньї-Улама^[en], варіанту гри «Двадцять запитань»,^[35] в якому відповіді можуть бути неправильними.^[36]

Квантовий двійковий пошук

Двійковий пошук на класичному комп'ютері обмежений найгіршим випадком, коли виконується рівно ${\textstyle \lfloor \log _{2}n+1\rfloor }$ ітерацій. Тоді як квантовий алгоритм двійкового пошуку виконується за кількість запитів (аналог ітерацій класичної процедури), пропорційній ${\textstyle \log _{2}n,}$ однак на відмінну від оригінального двійкового пошуку коефіцієнт пропорційності менший за одиницю. Будь-яка точна квантова процедура двійкового пошуку, тобто процедура, яка завжди дає правильний результат, вимагає принаймні ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$ запитів у найгіршому випадку, де ${\textstyle \ln }$ — натуральний логарифм.^[37] Існує точна процедура квантового двійкового пошуку, яка в найгіршому випадку виконується за ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ запитів.^[38]

Історія

Ідея сортування списку елементів для прискорення пошуку сягає ще античності. Найдавнішим відомим прикладом є табличка Інакібіт-Ану з Вавилону, що датується приблизно 200 роком до н. е. Табличка містить близько 500 шістдесяткових чисел та їхні обернені величини, відсортовані в лексикографічному порядку, що полегшує пошук конкретного запису. Крім того, на Егейських островах було виявлено кілька списків імен, відсортованих за першою літерою. Католикон^[en], латинський словник, завершений у 1286 році н. е., був першою книгою, в якій описувалися правила сортування слів в алфавітному порядку, а не лише за першими літерами.^[39]

У 1946 році Джон Моклі вперше згадав про двійковий пошук у рамках Лекцій школи Мура^[en], впливового та фундаментального курсу з інформатики для студентів коледжів.^[4] У 1957 році Вільям Веслі Петерсон^[en] опублікував перший метод інтерполяційного пошуку.^[4]^[40] Спочатку кожен опублікований алгоритм двійкового пошуку працював тільки для масивів, довжина яких на одиницю менша за степінь двійки, аж до 1960 року, коли Деррік Генрі Лемер^[en] опублікував алгоритм двійкового пошуку, який працював для будь-якого впорядкованого масиву.^[41] У 1962 році Герман Боттенбрух представив реалізацію цього алгоритму на мові ALGOL 60^[en], в якій перевірка на рівність виконувалася в кінці, що збільшувало середню кількість ітерацій на одиницю, але одночасно у кожній ітерації зменшувало на одне порівняння.^[3] Рівномірний двійковий пошук^[en] був запропонований А. К. Чандрою зі Стенфордського університету в 1971 році.^[4] У 1986 році Бернар Шазель^[en] та Леонідас Дж. Гібас^[en] запровадили дробове каскадування^[en] як метод розв'язання низки задач пошуку в обчислювальній геометрії.^[30]^[42]^[43]

Помилки в реалізації

Хоча базова ідея двійкового пошуку відносно проста, деталі можуть виявитися напрочуд хитрими
Оригінальний текст (англ.)
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky
— Дональд Кнут^[44]

Дослідження, опубліковане в 1988 році, виявило, що правильна реалізація двійкового пошуку міститься в п'яти з двадцяти розглянутих підручників.^[45] Код алгоритму в стандартній бібліотеці мови програмування Java мав помилку цілочисельного переповнення протягом більш ніж дев'яти років.^[46]

У практичних реалізаціях змінні, що використовуються для представлення індексів, часто мають фіксований розмір (наприклад, ціле число), що може призвести до цілочисельного переповнення для дуже великих масивів. Якщо індекс середини масиву обчислюється як ${\frac {L+R}{2}},$ то значення $L+R$ може перевищити діапазон типу даних, що використовується для його зберігання. Якщо $L$ та $R$ невід'ємні, то цього можна уникнути, обчислюючи індекс середини як $L+{\frac {R-L}{2}}.$ ^[47]

Див. також

Примітки

↑ ^а ^б Flores, Ivan; Madpis, George (1 вересня 1971). Average binary search length for dense ordered lists. Communications of the ACM. 14 (9): 602—603. doi:10.1145/362663.362752. ISSN 0001-0782. S2CID 43325465.
↑ ^а ^б ^в Knuth, 1998, pp. 409—411.
↑ ^а ^б ^в Bottenbruch, Hermann (1 квітня 1962). Structure and use of ALGOL 60. Journal of the ACM. 9 (2): 161—221. doi:10.1145/321119.321120. ISSN 0004-5411. S2CID 13406983. Процедура описана на с. 214 (§ 43) під назвою «Program for Binary Search».
↑ ^а ^б ^в ^г ^д Knuth, 1998, p. 422.
↑ ^а ^б Kasahara та Morishita, 2006, pp. 8—9.
↑ ^а ^б Sedgewick та Wayne, 2011, §3.1, підрозділ «Ранг та відбір» (англ. Rank and selection).
↑ ^а ^б Goldman та Goldman, 2008, pp. 461—463.
↑ Sedgewick та Wayne, 2011, §3.1, підрозділ «Запити за діапазоном» (англ. Range queries).
↑ Knuth, 1998, p. 413.
↑ ^а ^б Knuth, 1998, pp. 412—413.
↑ Knuth, 1998, pp. 413—414.
↑ Chang, 2003, p. 169.
↑ Knuth, 1998, p. 425.
↑ Rolfe, Timothy J. (1997). Analytic derivation of comparisons in binary search. ACM SIGNUM Newsletter. 32 (4): 15—19. doi:10.1145/289251.289255. S2CID 23752485.
↑ Knuth, 1997, §2.2.2. Послідовне розподілення (англ. Sequential Allocation).
↑ ^а ^б ^в Beame, Paul; Fich, Faith E. (2001). Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences. 65 (1): 38—72. doi:10.1006/jcss.2002.1822.
↑ Knuth, 1998, §6.2.1. Пошук у впорядкованій таблиці (англ. Searching an ordered table), підрозділ «Подальший аналіз двійкового пошуку» (англ. Further analysis of binary search).
↑ Knuth, 1998, Відповідь до вправи 5 з розділу §6.2.1.
↑ Sedgewick та Wayne, 2011, §3.2, підрозділ «Методи на основі порядку та видалення» (англ. Методи на основі порядку та видалення).
↑ Sedgewick та Wayne, 2011, §3.5, підрозділ «Яку реалізацію таблиці символів слід використовувати?» (англ. Which symbol-table implementation should I use?).
↑ Knuth, 1998, §6.4. Хешування (англ. Hashing).
↑ Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (Серпень 1994). Dynamic perfect hashing: upper and lower bounds. SIAM Journal on Computing. 23 (4): 738—761. doi:10.1137/S0097539791194094.
↑ Morin, Pat. Hash tables (PDF). с. 1. Архів оригіналу (PDF) за 9 жовтня 2022.
↑ Knuth, 2011, §7.1.3. Бітові трюки та техніки (англ. Bitwise Tricks and Techniques).
↑ Bloom, Burton H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM. 13 (7): 422—426. CiteSeerX 10.1.1.641.9096. doi:10.1145/362686.362692. S2CID 7931252.
↑ Knuth, 1998, pp. 414—416.
↑ Moffat та Turpin, 2002, p. 33.
↑ ^а ^б ^в Knuth, 1998, pp. 419—420.
↑ Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). Interpolation search—a log log n search. Communications of the ACM. 21 (7): 550—553. doi:10.1145/359545.359557. S2CID 11089655.
↑ ^а ^б Chazelle, Bernard; Liu, Ding (6 липня 2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. ACM. с. 322—329. doi:10.1145/380752.380818. ISBN 978-1-58113-349-3.
↑ Chazelle, Bernard; Liu, Ding (1 березня 2004). Lower bounds for intersection searching and fractional cascading in higher dimension (PDF). Journal of Computer and System Sciences (англ.). 68 (2): 269—284. CiteSeerX 10.1.1.298.7772. doi:10.1016/j.jcss.2003.07.003. ISSN 0022-0000. Архів (PDF) оригіналу за 9 жовтня 2022.
↑ Ben-Or, Michael; Hassidim, Avinatan (2008). The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) (PDF). 49th Symposium on Foundations of Computer Science. с. 221—230. doi:10.1109/FOCS.2008.58. ISBN 978-0-7695-3436-7. Архів (PDF) оригіналу за 9 жовтня 2022.
↑ Pelc, Andrzej (1989). Searching with known error probability. Theoretical Computer Science. 63 (2): 185—202. doi:10.1016/0304-3975(89)90077-7.
↑ Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures. 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351.
↑ Pelc, Andrzej (2002). Searching games with errors—fifty years of coping with liars. Theoretical Computer Science. 270 (1—2): 71—109. doi:10.1016/S0304-3975(01)00303-6.
↑ Rényi, Alfréd (1961). On a problem in information theory. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (англ.). 6: 515—516. MR 0143666.
↑ Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica. 34 (4): 429—448. arXiv:quant-ph/0102078. doi:10.1007/s00453-002-0976-3. S2CID 13717616.
↑ Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). Quantum algorithms for the ordered search problem via semidefinite programming. Physical Review A. 75 (3). 032335. arXiv:quant-ph/0608161. Bibcode:2007PhRvA..75c2335C. doi:10.1103/PhysRevA.75.032335. S2CID 41539957.
↑ Knuth, 1998, pp. 420—421.
↑ Peterson, William Wesley (1957). Addressing for random-access storage. IBM Journal of Research and Development. 1 (2): 130—146. doi:10.1147/rd.12.0130.
↑ Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Combinatorial Analysis. Proceedings of Symposia in Applied Mathematics. Т. 10. с. 180—181. doi:10.1090/psapm/010/0113289. ISBN 9780821813102. MR 0113289.
↑ Chazelle, Bernard; Guibas, Leonidas J. (1986). Fractional cascading: I. A data structuring technique (PDF). Algorithmica. 1 (1—4): 133—162. CiteSeerX 10.1.1.117.8349. doi:10.1007/BF01840440. S2CID 12745042.
↑ Chazelle, Bernard; Guibas, Leonidas J. (1986), Fractional cascading: II. Applications (PDF), Algorithmica, 1 (1—4): 163—191, doi:10.1007/BF01840441, S2CID 11232235
↑ Knuth, 1998, p. 410.
↑ Pattis, Richard E. (1988). Textbook errors in binary searching. SIGCSE Bulletin. 20: 190—194. doi:10.1145/52965.53012.
↑ Bloch, Joshua (2 червня 2006). Extra, extra – read all about it: nearly all binary searches and mergesorts are broken. Google Research Blog. Архів оригіналу за 1 квітня 2016.
↑ Ruggieri, Salvatore (2003). On computing the semi-sum of two integers (PDF). Information Processing Letters. 87 (2): 67—71. CiteSeerX 10.1.1.13.5631. doi:10.1016/S0020-0190(03)00263-1. Архів (PDF) оригіналу за 3 липня 2006.

Джерела

Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
Креневич А. П. Алгоритми і структури даних. — Київ : ВПЦ "Київський Університет", 2021. — 200 с.
Bentley, Jon (2000). Programming pearls (вид. 2nd). Addison-Wesley. ISBN 978-0-201-65788-3.
Butterfield, Andrew; Ngondi, Gerard E. (2016). A dictionary of computer science (вид. 7). Oxford, UK: Oxford University Press. ISBN 978-0-19-968897-5.
Chang, Shi-Kuo (2003). Data structures and algorithms. Software Engineering and Knowledge Engineering. Т. 13. Singapore: World Scientific. ISBN 978-981-238-348-8.
Fitzgerald, Michael (2015). Ruby pocket reference. Sebastopol, California: O'Reilly Media. ISBN 978-1-4919-2601-7.
Goldman, Sally A.; Goldman, Kenneth J. (2008). A practical guide to data structures and algorithms using Java. Boca Raton, Florida: CRC Press. ISBN 978-1-58488-455-2.
Kasahara, Masahiro; Morishita, Shinichi (2006). Large-scale genome sequence processing. London, UK: Imperial College Press. ISBN 978-1-86094-635-6.
Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)
Дональд Кнут. Combinatorial Algorithms, Part 1 // The Art of Computer Programming. — Massachusetts : Addison–Wesley, 2011. — Т. 4A. — 883 с. — ISBN 0-201-03804-8.(англ.)
Moffat, Alistair; Turpin, Andrew (2002). Compression and coding algorithms. Hamburg, Germany: Kluwer Academic Publishers. doi:10.1007/978-1-4615-0935-6. ISBN 978-0-7923-7668-2.
Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (вид. 4th). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-57351-3.
Б'ярне Страуструп (2013). The C++ Programming Language (англ.) (вид. 4). Addison-Wesley. ISBN 978-0321563842.
Ніклаус Вірт (2004) [1975]. Algorithms and Data Structures (PDF) (англ.). ETH Zürich. с. 366.

[FloresMadpis1971-1] а ^б Flores, Ivan; Madpis, George (1 вересня 1971). Average binary search length for dense ordered lists. Communications of the ACM. 14 (9): 602—603. doi:10.1145/362663.362752. ISSN 0001-0782. S2CID 43325465.

[FOOTNOTEKnuth1998409—411-2] а ^б ^в Knuth, 1998, pp. 409—411.

[Bottenbruch1962-3] а ^б ^в Bottenbruch, Hermann (1 квітня 1962). Structure and use of ALGOL 60. Journal of the ACM. 9 (2): 161—221. doi:10.1145/321119.321120. ISSN 0004-5411. S2CID 13406983. Процедура описана на с. 214 (§ 43) під назвою «Program for Binary Search».

[FOOTNOTEKnuth1998422-4] а ^б ^в ^г ^д Knuth, 1998, p. 422.

[FOOTNOTEKasaharaMorishita20068—9-5] а ^б Kasahara та Morishita, 2006, pp. 8—9.

[FOOTNOTESedgewickWayne2011§3.1,_підрозділ_«Ранг_та_відбір»_([[англійська_мова|англ.]]_<i_lang="en">Rank_and_selection</i>)-6] а ^б Sedgewick та Wayne, 2011, §3.1, підрозділ «Ранг та відбір» (англ. Rank and selection).

[FOOTNOTEGoldmanGoldman2008461—463-7] а ^б Goldman та Goldman, 2008, pp. 461—463.

[FOOTNOTESedgewickWayne2011§3.1,_підрозділ_«Запити_за_діапазоном»_([[англійська_мова|англ.]]_<i_lang="en">Range_queries</i>)-8] Sedgewick та Wayne, 2011, §3.1, підрозділ «Запити за діапазоном» (англ. Range queries).

[FOOTNOTEKnuth1998413-9] Knuth, 1998, p. 413.

[FOOTNOTEKnuth1998412—413-10] а ^б Knuth, 1998, pp. 412—413.

[FOOTNOTEKnuth1998413—414-11] Knuth, 1998, pp. 413—414.

[FOOTNOTEChang2003169-12] Chang, 2003, p. 169.

[FOOTNOTEKnuth1998425-13] Knuth, 1998, p. 425.

[14] Rolfe, Timothy J. (1997). Analytic derivation of comparisons in binary search. ACM SIGNUM Newsletter. 32 (4): 15—19. doi:10.1145/289251.289255. S2CID 23752485.

[FOOTNOTEKnuth1997§2.2.2._Послідовне_розподілення_([[англійська_мова|англ.]]_<i_lang="en">Sequential_Allocation</i>)-15] Knuth, 1997, §2.2.2. Послідовне розподілення (англ. Sequential Allocation).

[pred-16] а ^б ^в Beame, Paul; Fich, Faith E. (2001). Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences. 65 (1): 38—72. doi:10.1006/jcss.2002.1822.

[FOOTNOTEKnuth1998§6.2.1._Пошук_у_впорядкованій_таблиці_([[англійська_мова|англ.]]_<i_lang="en">Searching_an_ordered_table</i>),_підрозділ_«Подальший_аналіз_двійкового_пошуку»_([[англійська_мова|англ.]]_<i_lang="en">Further_analysis_of_binary_search</i>)-17] Knuth, 1998, §6.2.1. Пошук у впорядкованій таблиці (англ. Searching an ordered table), підрозділ «Подальший аналіз двійкового пошуку» (англ. Further analysis of binary search).

[FOOTNOTEKnuth1998Відповідь_до_вправи_5_з_розділу_§6.2.1-18] Knuth, 1998, Відповідь до вправи 5 з розділу §6.2.1.

[FOOTNOTESedgewickWayne2011§3.2,_підрозділ_«Методи_на_основі_порядку_та_видалення»_([[англійська_мова|англ.]]_<i_lang="en">Методи_на_основі_порядку_та_видалення</i>)-19] Sedgewick та Wayne, 2011, §3.2, підрозділ «Методи на основі порядку та видалення» (англ. Методи на основі порядку та видалення).

[FOOTNOTESedgewickWayne2011§3.5,_підрозділ_«Яку_реалізацію_таблиці_символів_слід_використовувати?»_([[англійська_мова|англ.]]_<i_lang="en">Which_symbol-table_implementation_should_I_use?</i>)-20] Sedgewick та Wayne, 2011, §3.5, підрозділ «Яку реалізацію таблиці символів слід використовувати?» (англ. Which symbol-table implementation should I use?).

[FOOTNOTEKnuth1998§6.4._Хешування_([[англійська_мова|англ.]]_<i_lang="en">Hashing</i>)-21] Knuth, 1998, §6.4. Хешування (англ. Hashing).

[22] Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (Серпень 1994). Dynamic perfect hashing: upper and lower bounds. SIAM Journal on Computing. 23 (4): 738—761. doi:10.1137/S0097539791194094.

[23] Morin, Pat. Hash tables (PDF). с. 1. Архів оригіналу (PDF) за 9 жовтня 2022.

[FOOTNOTEKnuth2011§7.1.3._Бітові_трюки_та_техніки_([[англійська_мова|англ.]]_<i_lang="en">Bitwise_Tricks_and_Techniques</i>)-24] Knuth, 2011, §7.1.3. Бітові трюки та техніки (англ. Bitwise Tricks and Techniques).

[25] Bloom, Burton H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM. 13 (7): 422—426. CiteSeerX 10.1.1.641.9096. doi:10.1145/362686.362692. S2CID 7931252.

[FOOTNOTEKnuth1998414—416-26] Knuth, 1998, pp. 414—416.

[FOOTNOTEMoffatTurpin200233-27] Moffat та Turpin, 2002, p. 33.

[FOOTNOTEKnuth1998419—420-28] а ^б ^в Knuth, 1998, pp. 419—420.

[29] Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). Interpolation search—a log log n search. Communications of the ACM. 21 (7): 550—553. doi:10.1145/359545.359557. S2CID 11089655.

[ChazelleLiu2001-30] а ^б Chazelle, Bernard; Liu, Ding (6 липня 2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. ACM. с. 322—329. doi:10.1145/380752.380818. ISBN 978-1-58113-349-3.

[ChazelleLiu2004-31] Chazelle, Bernard; Liu, Ding (1 березня 2004). Lower bounds for intersection searching and fractional cascading in higher dimension (PDF). Journal of Computer and System Sciences (англ.). 68 (2): 269—284. CiteSeerX 10.1.1.298.7772. doi:10.1016/j.jcss.2003.07.003. ISSN 0022-0000. Архів (PDF) оригіналу за 9 жовтня 2022.

[32] Ben-Or, Michael; Hassidim, Avinatan (2008). The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) (PDF). 49th Symposium on Foundations of Computer Science. с. 221—230. doi:10.1109/FOCS.2008.58. ISBN 978-0-7695-3436-7. Архів (PDF) оригіналу за 9 жовтня 2022.

[pelc1989-33] Pelc, Andrzej (1989). Searching with known error probability. Theoretical Computer Science. 63 (2): 185—202. doi:10.1016/0304-3975(89)90077-7.

[34] Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures. 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351.

[35] Pelc, Andrzej (2002). Searching games with errors—fifty years of coping with liars. Theoretical Computer Science. 270 (1—2): 71—109. doi:10.1016/S0304-3975(01)00303-6.

[36] Rényi, Alfréd (1961). On a problem in information theory. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (англ.). 6: 515—516. MR 0143666.

[37] Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica. 34 (4): 429—448. arXiv:quant-ph/0102078. doi:10.1007/s00453-002-0976-3. S2CID 13717616.

[quantumalgo-38] Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). Quantum algorithms for the ordered search problem via semidefinite programming. Physical Review A. 75 (3). 032335. arXiv:quant-ph/0608161. Bibcode:2007PhRvA..75c2335C. doi:10.1103/PhysRevA.75.032335. S2CID 41539957.

[FOOTNOTEKnuth1998420—421-39] Knuth, 1998, pp. 420—421.

[40] Peterson, William Wesley (1957). Addressing for random-access storage. IBM Journal of Research and Development. 1 (2): 130—146. doi:10.1147/rd.12.0130.

[41] Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Combinatorial Analysis. Proceedings of Symposia in Applied Mathematics. Т. 10. с. 180—181. doi:10.1090/psapm/010/0113289. ISBN 9780821813102. MR 0113289.

[42] Chazelle, Bernard; Guibas, Leonidas J. (1986). Fractional cascading: I. A data structuring technique (PDF). Algorithmica. 1 (1—4): 133—162. CiteSeerX 10.1.1.117.8349. doi:10.1007/BF01840440. S2CID 12745042.

[43] Chazelle, Bernard; Guibas, Leonidas J. (1986), Fractional cascading: II. Applications (PDF), Algorithmica, 1 (1—4): 163—191, doi:10.1007/BF01840441, S2CID 11232235

[FOOTNOTEKnuth1998410-44] Knuth, 1998, p. 410.

[textbook-45] Pattis, Richard E. (1988). Textbook errors in binary searching. SIGCSE Bulletin. 20: 190—194. doi:10.1145/52965.53012.

[46] Bloch, Joshua (2 червня 2006). Extra, extra – read all about it: nearly all binary searches and mergesorts are broken. Google Research Blog. Архів оригіналу за 1 квітня 2016.

[semisum-47] Ruggieri, Salvatore (2003). On computing the semi-sum of two integers (PDF). Information Processing Letters. 87 (2): 67—71. CiteSeerX 10.1.1.13.5631. doi:10.1016/S0020-0190(03)00263-1. Архів (PDF) оригіналу за 3 липня 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]