Как работает двоичный поиск и что он требует?

Question

Accepted Answer

**Binary search** находит цель в **отсортированном** массиве, многократно сокращая диапазон поиска вдвое. Каждое сравнение исключает половину оставшихся элементов, что дает время **O(log n)**. ## Идея Посмотрите на средний элемент. Если он равен целевому, готово. Если цель меньше, ищите в левой половине; если больше, ищите в правой половине. Повторяйте, пока не найдёте или диапазон не станет пуст. ## Пример ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## Трассировка ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Сложность - **Время:** O(log n). **Пространство:** O(1) итеративно. ## Подводные камни **Входные данные должны быть отсортированы** — иначе результаты бессмысленны. Следите за ошибками на единицу в `lo`/`hi` и переполнением целых чисел в некоторых языках (используйте `lo + (hi-lo)//2`). ## Почему это важно Уменьшение пространства поиска вдвое превращает поиск в массиве из миллиона элементов в ~20 сравнений. Паттерн разделяй и властвуй, лежащий в его основе, появляется снова в деревьях, базах данных и бесчисленных задачах на собеседованиях. Знание его одного жесткого требования — отсортированный ввод — защитит вас от классической тонкой ошибки.