Какая алгоритмическая сложность бинарного поиска
Что проверяют
Что вы знаете не только ответ O(log n), но и откуда он берётся, какие у алгоритма условия и сколько он стоит по памяти. В Go следом часто просят написать поиск без ошибок на границах или спрашивают, что уже есть в стандартной библиотеке.
Как отвечать
- время: O(log n). Каждое сравнение отбрасывает половину диапазона, поэтому в худшем случае нужно ⌊log₂ n⌋ + 1 проверок: для 16 элементов это 5, для миллиона около 20, для миллиарда около 30;
- память: O(1) у итеративной версии. Рекурсивная тратит O(log n) стека, а Go хвостовую рекурсию не оптимизирует;
- условие: слайс отсортирован по тому же критерию, по которому ищете. Сортировка стоит O(n log n), поэтому окупается, только если искать предстоит многократно;
- стандартная библиотека:
slices.BinarySearch(s, x)с Go 1.21 возвращает позицию и флагfound;sort.Search(n, f)находит наименьший индекс, гдеf(i)истинно, и возвращаетn, если такого нет. Для своих типов естьslices.BinarySearchFunc.
Середину считайте как lo + (hi-lo)/2, а не (lo+hi)/2. На 64-битном int переполнение маловероятно, но интервьюер ждёт, что вы знаете про эту ловушку.
Если элементы повторяются, классический поиск вернёт любой из равных. Для первого вхождения нужен вариант lower bound: при совпадении не выходить из цикла, а сдвигать правую границу. Именно так ведёт себя sort.Search.
Хороший финал: где это встречается на практике. Поиск записи по времени в упорядоченном журнале, версии в отсортированном списке релизов, диапазона в таблице IP-адресов.
Где спотыкаются
Путают границы: пишут lo < hi вместе с hi = mid-1 или забывают +1 при сдвиге левой границы. Итог: пропущенный последний элемент или бесконечный цикл на двух элементах.
Не проверяют результат sort.Search. Функция возвращает точку вставки, а не факт находки, поэтому нужна проверка i < len(a) && a[i] == x.
Считают, что логарифм даётся на любых данных. На несортированном слайсе поиск не упадёт, а молча вернёт неверный ответ, и на связном списке O(log n) тоже не получится.