Что такое linear search и binary search?
На этой странице
Linear search проверяет элементы по одному и работает за O(n). Binary search работает за O(log n), но требует отсортированного пространства поиска и на каждом шаге отбрасывает половину вариантов.
Вопрос
Чем linear search отличается от binary search и когда применим бинарный поиск?
Linear search
function linearSearch(nums: number[], target: number): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i
}
return -1
}Сложность:
Time: O(n)
Space: O(1)Binary search
function binarySearch(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
while (left <= right) {
const mid = left + Math.floor((right - left) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) left = mid + 1
else right = mid - 1
}
return -1
}Сложность:
Time: O(log n)
Space: O(1)Binary search похож на поиск слова в бумажном словаре: открываем середину, смотрим, левее или правее нужное слово, и отбрасываем половину.
Пример: nums = [1, 3, 5, 7, 9, 11, 13], target = 11.
| left | right | mid | nums[mid] | Действие |
|---|---|---|---|---|
| 0 | 6 | 3 | 7 | 7 < 11, ответ правее: left = 4 |
| 4 | 6 | 5 | 11 | нашли, вернуть 5 |
Пример, когда элемента нет: target = 4.
| left | right | mid | nums[mid] | Действие |
|---|---|---|---|---|
| 0 | 6 | 3 | 7 | 7 > 4, right = 2 |
| 0 | 2 | 1 | 3 | 3 < 4, left = 2 |
| 2 | 2 | 2 | 5 | 5 > 4, right = 1 |
| 2 | 1 | - | - | left > right, диапазон пуст, вернуть -1 |
Почему mid + 1 и mid - 1, а не mid? Элемент nums[mid] мы уже проверили, его можно исключить. Если оставить left = mid, на двух элементах цикл может никогда не закончиться.
Запись left + Math.floor((right - left) / 2) дает то же, что Math.floor((left + right) / 2). В JS разницы нет, но в языках с 32-битными целыми left + right может переполниться, поэтому первую форму часто пишут по привычке.
Подробнее про границы - в уроке Как избегать off by one.
Главное условие binary search
Binary search работает, когда можно отбросить половину поиска.
Обычно это:
- отсортированный массив;
- монотонная функция;
- диапазон ответов;
- задача "найти минимальное значение, при котором условие true".
Что отвечать на собеседовании?
Linear search подходит для неотсортированных данных и работает за O(n). Binary search требует отсортированного или монотонного пространства поиска и работает за O(log n), потому что на каждом шаге уменьшает область поиска вдвое.
Что важно помнить: частые ошибки
- Использовать binary search на неотсортированном массиве.
- Ошибаться в условии
left <= right. - Делать
mid = (left + right) / 2безMath.floor. - Получать бесконечный цикл из-за неправильного обновления границ.
- Не понимать binary search по answer space.
Мини-шпаргалка
- Linear search -
O(n). - Binary search -
O(log n). - Binary требует порядок/монотонность.
left,right,mid.- Обновляй границы строго.
- Возвращай
-1или agreed fallback.