Що таке бінарне пошук?
У комп'ютерній науці бінарний пошук, також відомий як пошук напівінтервала, логарифмічний пошук або бінарний розріз, є алгоритмом пошуку, який знаходить позицію цільової вартості в сортуваному матриці. Бінарний пошук порівнює цільове значення з середнім елементом масиву. Якщо вони не дорівнюють, половина, в якій ціль не може лежати, усувається, а пошук продовжується на іншій половині, знову беручи середній елемент для порівняння з цільовим значенням, і повторюючи це, поки не знайдено цільове значення. Якщо пошук закінчується залишковою половиною порожньою, ціль не знаходиться в матриці.

Бінарний пошук працює в логарифмічному часі в найгіршому випадку, роблячи

O(log n) порівняння, де

n - кількість елементів в матриці. Бінарне пошук швидше, ніж лінійне пошук, за винятком невеликих матриць. Однак матрицю необхідно спершу сортувати, щоб застосувати бінарний пошук. Існують спеціалізовані структури даних, призначені для швидкого пошуку, такі як хеш-таблиці, які можна шукати більш ефективно, ніж бінарне пошук. Однак бінарне пошук може вирішити більш широкий спектр проблем, таких як пошук наступного найменшого або наступного найбільшого елемента в матриці по відношенню до цілі, навіть якщо він відсутній в матриці.

Існує багато варіантів бінарного пошуку. Зокрема, фракційне каскадування прискорює бінарні пошуки того ж значення в декількох матрицях. Фракційне каскадування ефективно вирішує кілька проблем пошуку в обчислювальній геометрії та численних інших областях. Експоненціальне пошук розширює бінарне пошук до необмежених списків. Двостороннє дерево пошуку і структури даних B-дерева засновані на двосторонньому пошуку.
Бінарне пошук - це алгоритм пошуку, який знаходить позицію цільової вартості в сортуваному матриці. Вона усуває половину, в якій цільове значення не може лежати. Він шукає значення в іншій половині. Це продовжується, повторюючи середній елемент для порівняння з цільовим значенням, поки не буде знайдено цільове значення.
Бінарне пошук швидше, ніж лінійне пошук, за винятком невеликих матриць.