Бинарный поиск: три места, где он ломается
Бинарный поиск пишется за пять минут, но ошибиться в нём легко. Разбирал его для статьи и выписал три места, где он ломается.
Идея простая: в отсортированных данных смотрим в середину и отбрасываем половину. Миллион элементов - максимум 20 шагов, перебор в худшем случае проверит весь миллион.
Где ломается:
1. Границы. high = len - 1, а не len, и условие цикла low <= high. Чуть иначе - и либо выход за границы среза, либо последний кандидат так и не проверится.
2. Середина. Строку mid := (low + high) / 2 любят разбирать на собеседованиях: в других языках сумма может переполниться, поэтому пишут low + (high - low) / 2. В Go на 64-битной системе int 64-битный, на практике это не грозит, но объяснить стоит уметь.
3. Дубликаты. Самописный вариант не гарантирует, какой из одинаковых элементов найдёт. Нужен первый - есть slices.BinarySearch из стандартной библиотеки (с Go 1.21).
Полный разбор с кодом и трассировкой по шагам
Какой из трёх пунктов чаще всплывает у вас - границы, переполнение или дубликаты?
