Перш ніж ми вивчимо бінарний пошук, давайте дізнаємось:
Що таке пошук?
Пошук - це утиліта, яка дозволяє користувачеві знаходити документи, файли, носії інформації або будь-який інший тип даних, що зберігаються всередині бази даних. Пошук працює за простим принципом узгодження критеріїв із записами та відображення їх користувачеві. Таким чином працює найпростіша функція пошуку.
Що таке двійковий пошук?
Двійковий пошук - це вдосконалений тип алгоритму пошуку, який знаходить і отримує дані з відсортованого списку елементів. Його основний принцип роботи передбачає поділ даних у списку навпіл, поки необхідне значення не буде знайдено та не відображено користувачеві в результатах пошуку. Бінарний пошук загальновідомий як пошук із напівінтервалами або логарифмічний пошук .
У цьому посібнику з алгоритму ви дізнаєтесь:
- Що таке пошук?
- Що таке двійковий пошук?
- Як працює двійковий пошук?
- Приклад двійкового пошуку
- Навіщо нам потрібен двійковий пошук?
Як працює двійковий пошук?
Двійковий пошук працює наступним чином:
- Процес пошуку розпочинається шляхом пошуку середнього елемента відсортованого масиву даних
- Після цього ключове значення порівнюється з елементом
- Якщо значення ключа менше середнього елемента, пошук здійснює аналіз верхніх значень середнього елемента для порівняння та узгодження
- Якщо значення ключа більше, ніж середній елемент, тоді пошук аналізує нижчі значення середнього елемента для порівняння та узгодження
Приклад двійкового пошуку
Давайте розглянемо приклад словника. Якщо вам потрібно знайти певне слово, ніхто не проходить кожне слово послідовно, а випадковим чином визначає найближчі слова для пошуку потрібного слова.
Наведене зображення ілюструє наступне:
- У вас є масив із 10 цифр, і елемент 59 потрібно знайти.
- Всі елементи позначені індексом від 0 до 9. Тепер обчислюється середина масиву. Для цього ви берете крайнє ліве та праве значення індексу та ділите їх на 2. Результат - 4,5, але ми беремо нижнє значення. Отже, середина дорівнює 4.
- Алгоритм опускає всі елементи від середньої (4) до найнижчої межі, оскільки 59 більше 24, і тепер масив залишив лише 5 елементів.
- Тепер 59 більше 45 і менше 63. Середина дорівнює 7. Отже, значення правого індексу стає середнім - 1, що дорівнює 6, а значення лівого індексу залишається таким же, як і раніше, тобто 5.
- На цьому етапі ви знаєте, що 59 приходить після 45. Отже, лівий індекс, який дорівнює 5, також стає середнім.
- Ці ітерації тривають до тих пір, поки масив не зменшиться лише до одного елемента, або елемент, який буде знайдено, стане серединою масиву.
Приклад 2
Давайте розглянемо наступний приклад, щоб зрозуміти, як працює двійковий пошук
- У вас є масив відсортованих значень від 2 до 20, і вам потрібно знайти 18.
- Середнє значення нижньої та верхньої меж становить (l + r) / 2 = 4. Значення, яке шукається, більше середнього, що дорівнює 4.
- Значення масиву, менші за середнє, випадають із пошуку та шукають значення, більші за середнє значення 4.
- Це повторюваний процес поділу, поки не буде знайдений фактичний предмет, який потрібно шукати.
Навіщо нам потрібен двійковий пошук?
Наступні причини роблять бінарний пошук кращим вибором для використання в якості алгоритму пошуку:
- Бінарний пошук ефективно працює з відсортованими даними незалежно від їх розміру
- Замість того, щоб виконувати пошук, переглядаючи дані послідовно, двійковий алгоритм випадковим чином отримує доступ до даних, щоб знайти необхідний елемент. Це робить цикли пошуку коротшими та точнішими.
- Бінарний пошук виконує порівняння відсортованих даних на основі принципу впорядкування, ніж використання порівнянь рівності, які є більш повільними та переважно неточними.
- Після кожного циклу пошуку алгоритм ділить розмір масиву на половину, отже, на наступній ітерації він буде працювати лише на решті половини масиву
Резюме
- Пошук - це утиліта, яка дозволяє користувачеві шукати документи, файли та інші типи даних. Двійковий пошук - це вдосконалений тип алгоритму пошуку, який знаходить і отримує дані з відсортованого списку елементів.
- Бінарний пошук загальновідомий як пошук із напівінтервалами або логарифмічний пошук
- Це працює шляхом ділення масиву навпіл на кожній ітерації під знайденим необхідним елементом.
- Двійковий алгоритм приймає середину масиву, поділивши суму лівого та крайнього правого значень індексу на 2. Тепер алгоритм опускає або нижню, або верхню межу елементів із середини масиву, залежно від елемента, який потрібно знайти .
- Алгоритм випадково отримує доступ до даних, щоб знайти необхідний елемент. Це робить цикли пошуку коротшими та точнішими.
- Двійковий пошук виконує порівняння відсортованих даних на основі принципу впорядкування, ніж використання порівнянь рівності, які є повільними та неточними.
- Двійковий пошук не підходить для невідсортованих даних.