Easybinary-search
Как работают бинарный поиск и его сложность?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Бинарный поиск — поиск в отсортированном массиве делением пополам: сравниваем middle с target и отбрасываем половину. Сложность O(log n) по времени, O(1) по памяти.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Требование: массив отсортирован. Вариации: lower_bound (первая позиция вставки), upper_bound, поиск в rotated sorted array, бинарный поиск на ответе для optimization problems. Библиотеки: bisect в Python, std::lower_bound в C++, Arrays.binarySearch в Java.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.