Двоичный поиск

Допустим нам необходимо узнать относится ли адрес электронной почты “demensdeum@gmail.com”  к списку разрешенных email адресов для получения писем.

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

Для ответа на этот вопрос используют “Временную сложность алгоритмов”, “О” нотацию. Время работы линейного поиска в худшем случае равно n-му количеству элементов массива, напишем это в “О” нотации – O(n). Далее нужно пояснить что для любого известного алгоритма есть три показателя производительности – время выполнения в лучшем, худшем и среднем случае. Например адрес почты “demensdeum@gmail.com” находится в первом индексе массива, тогда он будет найден за первый шаг алгоритма, из этого следует что время выполнения в лучшем случае – O(1); а если в конце списка, то это худший случай – O(n)

Но как же детали реализации ПО, производительность железа, они ведь должны влиять на big O? А теперь выдохните и представьте что расчет временной сложности рассчитывается для некой абстрактной идеальной машины, в которой есть только этот алгоритм и больше ничего.

Алгоритм

Ок, получается что линейный поиск достаточно медленный, попробуем использовать Бинарный поиск. Для начала следует пояснить что с бинарными данными мы работать не будем, такое название данному методу дано из-за особенностей его работы. Изначально мы сортируем массив в лексикографическом порядке, затем алгоритм берет диапазон всего массива, получает средний элемент диапазона, сравнивает его лексикографически, и в зависимости от результата сравнения решает какой диапазон брать для поиска дальше – верхнюю половину текущего или нижнюю. То есть на каждом шаге поиска принимается решение из двух возможных – бинарная логика. Этот шаг повторяется до тех пор, пока либо слово найдется, либо не найдется (произойдет пересечение нижнего и верхних индексов диапазона).

Производительность данного алгоритма – лучший случай когда сразу найден элемент в середине массива O(1), худший случай перебора O(log n)

Подводные камни

При реализации бинарного поиска я встретился мало того с интересной проблемой отсутствия стандартизации лексикографического сравнения в библиотеках языков программирования, но даже обнаружил отсутствие единого стандарта реализации localeCompare внутри JavaScript. Стандарт ECMAScript допускает разную реализацию данной функции, из-за этого при сортировке с помощью localeCompare, на разных движках JavaScript может наблюдаться абсолютно разный результат.

Поэтому для корректной работы алгоритма нужно обязательно сортировать и использовать в работе только один и тот же алгоритм лексикографического сравнения, иначе работать ничего не будет. Со-но если например попытаться сортировать массив в Scala, а искать с помощью nodejs, не реализуя собственную сортировку/сортировку одной реализации, то кроме разочарования в человечестве вас ничего не ждет.

Источники

Что такое лексикографическое сравнение и что оно собой представляет?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript

Исходный код

https://gitlab.com/demensdeum/algorithms