Алгоритм бінарного пошуку з ПРИКЛАДОМ

Перш ніж ми вивчимо бінарний пошук, давайте дізнаємося, що таке пошук.

Що таке пошук?

Пошук — це утиліта, яка дозволяє користувачеві знаходити документи, файли, медіафайли чи будь-які інші типи даних, що містяться в базі даних. Пошук працює за простим принципом зіставлення критеріїв із записами та відображення їх користувачеві. Таким чином працює найпростіша функція пошуку.

Що таке двійковий пошук?

Бінарний пошук – це розширений тип алгоритму пошуку, який знаходить та вибирає дані з відсортованого списку елементів. Його основний принцип роботи полягає в тому, щоб поділити дані у списку навпіл, доки не буде знайдено потрібне значення, яке не відобразиться користувачеві в результаті пошуку. Бінарний пошук зазвичай відомий як півінтервальний пошук або логарифмічний пошук.

Як працює бінарний пошук?

Двійковий пошук працює таким чином:

• Процес пошуку починається з визначення середнього елемента відсортованого масиву даних.
• Після цього значення ключа порівнюється з елементом.
• Якщо значення ключа менше, ніж середній елемент, то пошук аналізує верхні значення до середнього елемента для порівняння та зіставлення.
• Якщо значення ключа більше, ніж середній елемент, то пошук аналізує нижчі значення середнього елемента для порівняння та зіставлення.

Алгоритм бінарного пошуку (псевдокод)

Бінарний пошук можна записати як коротку ітераційну процедуру. Вона зберігає два вказівники, низький і високий, і звужує діапазон, доки ціль не буде знайдена або діапазон не стане порожнім.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

У разі успіху підпрограма повертає індекс цілі та -1, якщо значення відсутнє. Оскільки діапазон зменшується вдвічі на кожному проході, цикл виконується не більше log₂(n) разів.

Приклад двійкового пошуку

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

Наведене вище зображення ілюструє наступне:

1. У вас є масив з 10 цифр, і потрібно знайти елемент 59.
2. Усі елементи позначені індексом від 0 до 9. Тепер обчислюється середина масиву. Для цього потрібно взяти ліве та праве значення індексу та поділити їх на 2. Результат дорівнює 4.5, але ми беремо значення підлоги. Отже, середина дорівнює 4.
3. Алгоритм видаляє всі елементи від середини (4) до нижньої межі, оскільки 59 більше за 24, і тепер масив залишається лише з 5 елементами.
4. Тепер 59 більше за 45 і менше за 63. Середина дорівнює 7. Отже, значення правого індексу стає середнім -1, що дорівнює 6, а значення лівого індексу залишається таким самим, як і раніше, тобто 5.
5. У цей момент ви знаєте, що 59 йде після 45. Отже, лівий індекс, який дорівнює 5, також стає середнім.
6. Ці ітерації тривають до тих пір, поки масив не скоротиться лише до одного елемента, або елемент, який потрібно знайти, не стане серединою масиву.

Приклад 2

Давайте розглянемо наступний приклад, щоб зрозуміти, як працює бінарний пошук.

1. У вас є масив відсортованих значень від 2 до 20, вам потрібно знайти 18.
2. Середнє значення нижньої та верхньої меж дорівнює (l + r) / 2 = 4. Шукане значення більше за середнє, яке дорівнює 4.
3. Значення масиву, менші за середнє значення, виключаються з пошуку, а значення, більші за середнє значення 4, шукаються.
4. Це повторюваний процес поділу, доки не буде знайдено фактичний предмет, який потрібно шукати.

Навіщо нам двійковий пошук?

Наступні причини роблять бінарний пошук кращим вибором для використання як алгоритму пошуку:

• Бінарний пошук ефективно працює з відсортованими даними незалежно від їх розміру.
• Замість виконання пошуку, переглядаючи дані в послідовності, двійковий алгоритм випадково отримує доступ до даних, щоб знайти потрібний елемент. Це робить цикли пошуку коротшими та точнішими.
• Бінарний пошук виконує порівняння відсортованих даних на основі принципу впорядкування, а не використовує порівняння на рівність, які є повільнішими та здебільшого неточними.
• Після кожного циклу пошуку алгоритм ділить розмір масиву навпіл; отже, на наступній ітерації він працюватиме лише з рештою половини масиву.

Дізнайтеся наш наступний навчальний посібник про Лінійний пошук: Python, C++ Приклад.

Бінарний пошук проти лінійного пошуку

Бінарний пошук та лінійний пошук – це два найпоширеніші способи пошуку значення в колекції. У таблиці нижче показано, чим вони відрізняються:

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

Поширені запитання