Бинарный поиск
Быстрый способ поиска в отсортированном массиве: каждый шаг делит диапазон пополам.
Идея алгоритма
Мы берём середину отсортированного массива и сравниваем её с тем, что ищем. Если искомое число меньше середины — продолжаем искать только в левой половине, если больше — в правой. На каждом шаге диапазон уменьшается в два раза, поэтому поиск идёт очень быстро.
Асимптотика:
- Время (любой случай): O(log n)
- Память: O(1)
- Требуется предварительно отсортированный массив.
Плюсы
- Работает гораздо быстрее линейного поиска на больших данных;
- Простая идея, легко визуализировать и запомнить;
- Часто используется в задачах олимпиадного и интервью-уровня.
Минусы
- Работает только с отсортированными данными;
- Легко ошибиться в границах и середине (off-by-one ошибки);
- При частых изменениях массива сортировку придётся обновлять.
Пример кода
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания