Найти тему
Golang

Бинарный поиск в Go

В этой статье я хочу показать вам алгоритм бинарного поиска и его реализацию в Go.

Что такое бинарный поиск?

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

  1. Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
  2. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
  3. Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
  4. Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.

  • Что будет, если 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)

-2

Как реализовать бинарный поиск в Go?

К счастью, нам не нужно самим реализовывать бинарный поиск в Go, потому что пакет sort стандартной библиотеки Go уже поставляется с реализацией алгоритма бинарного поиска.

Стандартная библиотека Go написана на Go (я знаю, это ошеломляет) и имеет открытый исходный код, давайте взглянем на него:

-3

Код

Давайте разберем код.

Функция поиска принимает два параметра:

n: длина массива

f: функция сравнения, возвращающая true или false. В нашем случае эта функция вернет значение, если элемент заданного индекса массива больше целевого элемента.

На практике вышеуказанная функция может использоваться для выполнения бинарного поиска следующим образом:

-4

Код

Для удобства мы можем сократить код, используя функцию sort.SearchInts:

-5

Код

Еще один пример реализации бинарного поиска:

-6

Код

Golang
Go tests

Наука
7 млн интересуются