Бинарный поиск один из самых популярных и простых алгоритмов поиска. Он активно используется во многих системах, например в базах данных для быстрого поиска и индексирования.

Первое что нужно знать — алгоритм работает только на отсортированных данных. Поэтому перед поиском нужно отсортировать массив.

Начинается алгоритм с того что берем элемент из середины массива и сравниваем с искомым значением. Если искомый элемент больше среднего, тогда искомое значение лежит в правой части массива. Идем в правую часть массива, опять берем элемент из середины и сравниваем его с искомым. В этот раз искомый элемент меньше среднего, тогда он скорее всего находится в левой части этого под массива.

Таким образом мы постоянно сравниваем искомое значение со значением из середины массива. После этого откидываем половину значений. Это здорово ускоряет поиск, потому что не нужно проверять все элементы массива. На каждом этапе отбрасывается половина элементов.

В итоге всех операций наступает момент когда искать приходиться в массиве из одного элемента. В таком случае просто сравниваем с искомым, если равны, тогда мы нашли элемент, если не, тогда не нашли.

А теперь живой пример. Есть отсортированный массив и нужно найти число 9. Берем элемент из середины — 8, сравниваем, 9 больше 8, значит нужно продолжить поиск в правой части.

Снова берем элемент из середины — 11, 9 меньше 11, значит нужно искать в левой части нашего подмассива.

Берем элемент из середины — 9, сравниваем, элементы равны, число 9 есть в массиве и храниться по индексу 4. Мы нашли нужный элемент всего за 3 шага.

Если пробовать оценить скорость работы алгоритма, то получается что она равна O(log n). Для сравнения, обычный поиск перебором имеет скорость O(n), это значит что нужно перебрать все элементы массива. Что это значит на практике?

Посмотреть реализацию на C# можно на dotnetfiddle.

Как оптимизировать сортировку?

Массив всегда должен быть отсортированным чтобы поиск работал, а это значит что при каждом добавлении нового элемента нужно запускать сортировку. Возникает вопрос, а что если сразу вставлять новый элемент в правильное место? Тогда у нас всегда будет отсортированный массив и не нужно каждый раз прогонять сортировку.

Так же подумали умные ребята и придумали бинарное дерево поиска. Это структура данных, которая основывается на работе бинарного поиска. По сути это реализация бинарного поиска в виде структуры данных.

Структура дерева достаточно простая: каждый элемент может иметь только два дочерних элемента. Их еще часто называют левым и правым. В левом дочернем элементе храниться значение, меньше чем в родительском, а в правом — больше.

Как работает поиск в дереве?

Сравниваем искомое значение со значением в корневом элементе. Если оно больше, тогда мы идем к правому дочернему элементу и повторяем процедуру. Таким образом мы начинаем с самого верха и плавно опускаемся пока не найдем элемент с таким же значением.

Вставка нового элемента работает так же как и поиск. Сравниваем новый элемент с текущим и опускаемся по дереву вниз пока не найдем подходящее место. В итоге при каждом добавлении у нас будет отсортированный набор данных.

Но что будет если всегда добавлять элементы с все большим и большим значением? Наше дерево будет выглядеть вот так:

По сути для поиска значения на нужно обойти все элементы дерева, а это значит что скорость работы упадет до O(n). Получается что бинарное дерево поиска в среднем работает со скоростью O(log n), а в худшем O(n).

Такие деревья еще называют не сбалансированными. Чтобы исправить ситуацию существуют специальные алгоритмы балансировки деревьев, которые приводят их в нормальный вид. Но рассматривать здесь я их не буду.

Итог

Бинарный поиск один из самых простых и элегантных алгоритмов поиска, который привел к созданию новой структуры данных — бинарного дерева поиска. Данная структура является очень популярной и используется по многих системах. Особенно активно в базах данных для создания индексов и оптимизации выборки данных.

Если тема интересная, то можно копнуть дальше и разобраться с:

• Красно черными деревьями
• Кучами
• B-деревьями
• и т. д.

Бонус

На сайте https://idea-instructions.com есть объяснения разных алгоритмов в стиле инструкций с икеи. Например AVL дерево