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

O(n) час для кожної такої операції. Крім того, сортовані матриці можуть ускладнювати використання пам'яті, особливо коли елементи часто вставляються в матрицю. Є й інші структури даних, які підтримують набагато більш ефективне введення та видалення. Бінарний пошук може бути використаний для виконання точного відповідності та встановлення членства (визначення того, чи є цільове значення в наборі цінностей). Існують структури даних, які підтримують більш швидке точне зіставлення і встановлення членства. Однак, на відміну від багатьох інших пошукових схем, бінарний пошук може бути використаний для ефективного приблизного відповідності, зазвичай виконуючи такі відповіді в
O(log n) час незалежно від типу або структури самих значень. Крім того, існують деякі операції, такі як пошук найменшого і найбільшого елемента, які можна ефективно виконувати на сольованій матриці.

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

Лінійне пошук - це простий алгоритм пошуку, який перевіряє кожен запис, поки не знайде цільове значення. Лінійне пошук можна зробити на пов'язаному списку, що дозволяє швидше вставити і видалити, ніж матриці. Бінарний пошук швидше, ніж лінійний пошук для сортуваних матриць, за винятком випадків, коли матриця коротка, хоча матрицю потрібно сортувати заздалегідь. Всі алгоритми сортування, засновані на порівняльних елементах, такі як quicksort і merge sort, вимагають принаймні
O(nlog n) порівняння в найгіршому випадку. На відміну від лінійного пошуку, бінарний пошук може бути використаний для ефективного приблизного відповідності. Існують такі операції, як пошук найменшого і найбільшого елемента, які можна зробити ефективно на сортованій матриці, але не на несортованій матриці.

Дерева :

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

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

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

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

Розробка алгоритмів членства:
Проблемою, пов'язаною з пошуком, є встановлення членства. Будь-який алгоритм, який робить пошук, як бінарний пошук, також може бути використаний для встановлення членства. Є й інші алгоритми, які більш конкретно підходять для встановленого членства. Біт матриця є найпростішим, корисним, коли діапазон ключів обмежений. Він компактно зберігає колекцію бітів, причому кожен біт являє собою єдиний ключ у діапазоні ключів. Біткоіни дуже швидкі, вимагають тільки
Тип Judy1 матриці Judy ефективно обробляє 64-бітні ключі.

Для приблизних результатів фільтри Блума, інша ймовірна структура даних, заснована на хешінгу, зберігає набір ключів, кодуючи ключі за допомогою бітової матриці та декількох хеш-функцій. Фільтри Bloom набагато більш простороефективні, ніж бітові масиви в більшості випадків, і не набагато повільніше: з
к хеш-функції, запити на членство вимагають тільки
О (k) час Однак фільтри Bloom страждають від фальшивих позитивних.

Інші структури даних:
Існують структури даних, які можуть покращитися на бінарному пошуку в деяких випадках як для пошуку, так і для інших операцій, доступних для сортованих масивів. Наприклад, пошуки, приблизні відповіді та операції, доступні для сортованих матриць, можуть бути виконані більш ефективно, ніж двосторонній пошук на спеціалізованих структурах даних, таких як дерева van Emde Boas, дерева злиття, проби і бітові матриці. Ці спеціалізовані структури даних зазвичай тільки швидше, тому що вони використовують властивості ключів з певним атрибутом (зазвичай ключі, які є невеликими цілими числами), і, таким чином, буде витрачати час або простір для ключів, які не мають цього атрибуту. Поки ключі можуть бути упорядковані, ці операції завжди можуть бути виконані принаймні ефективно на сортованому матриці незалежно від ключів. Деякі структури, такі як матриці Джуді, використовують комбінацію підходів, щоб пом'якшити це, зберігаючи при цьому ефективність і здатність виконувати приблизні збіги.
Сортовані масиви з бінарним пошуком є дуже неефективним рішенням, коли операції введення та видалення переплітаються з пошуком. Крім того, сортовані матриці можуть ускладнювати використання пам'яті, особливо коли елементи часто вставляються в матрицю.
Бінарний пошук швидше, ніж лінійний пошук для сортуваних матриць, за винятком випадків, коли матриця коротка, хоча матрицю потрібно сортувати заздалегідь.
Бінарний пошук зазвичай більш ефективний для пошуку, оскільки дерева бінарного пошуку, швидше за все, будуть недосконало збалансовані, що призводить до трохи гіршої продуктивності, ніж бінарний пошук.
Структура даних, яка відображає ключі до записів за допомогою хеш-функції, як правило, швидше, ніж бінарне пошук на сортуваному матриці записів.