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

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

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

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

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

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

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

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

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

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

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

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

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++ Приклад

Підсумки

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