В этой статье я хочу показать вам алгоритм бинарного поиска и его реализацию в Go.
Что такое бинарный поиск?
Бинарный поиск — это быстрый и простой алгоритм, который находит целевой элемент в отсортированном массиве путем многократного деления интервала поиска пополам.
- Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
- Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
- Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
- Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.
- Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет?
- Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
Использовать код first + (last - first) / 2, который точно не приведёт к переполнениям (то и другое — неотрицательные целые числа).Если first и last — указатели или итераторы, такой код единственно правильный. Преобразование в uintptr_t и дальнейший расчёт в этом типе нарушает абстракцию, и нет гарантии, что результат останется корректным указателем. Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «итератор+число → итератор», «итератор−итератор → число».
Если first и last — типы со знаком, провести расчёт в беззнаковом типе: ((unsigned)first + (unsigned)last) / 2 - (first + last) >>> 1.
Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие add eax, b; rcr eax, 1. А вот длинные типы использовать нецелесообразно, first + (last - first) / 2 быстрее. - В бинарном поиске часты ошибки на единицу. Поэтому важно протестировать такие случаи: пустой массив (n=0), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Не выходит ли алгоритм за границы массива? Не зацикливается ли?
- Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).
Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая бинарый поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям.
Давайте посмотрим, как это делается:
Начальный интервал поиска - весь массив
Мы берем элемент в середине интервала и сравниваем его с целевым элемнтом. Если он меньше , мы сужаем интервал до верхней половины.
В противном случае мы сужаем интервал до нижней половины.
Повторяем вышеуказанные шаги до тех пор, пока интервалы не охватят только один элемент и не вернут индекс массива этого элемента.
Сложность алгоритма (в худшем случае): O (log n)
Как реализовать бинарный поиск в Go?
К счастью, нам не нужно самим реализовывать бинарный поиск в Go, потому что пакет sort стандартной библиотеки Go уже поставляется с реализацией алгоритма бинарного поиска.
Стандартная библиотека Go написана на Go (я знаю, это ошеломляет) и имеет открытый исходный код, давайте взглянем на него:
Давайте разберем код.
Функция поиска принимает два параметра:
n: длина массива
f: функция сравнения, возвращающая true или false. В нашем случае эта функция вернет значение, если элемент заданного индекса массива больше целевого элемента.
На практике вышеуказанная функция может использоваться для выполнения бинарного поиска следующим образом:
Для удобства мы можем сократить код, используя функцию sort.SearchInts:
Еще один пример реализации бинарного поиска: