Binary Search (Бинарный поиск)
Когда применять:
- Входной массив отсортирован.
- Нужно найти элемент за O(log n).
- Monotonic Function: Ответ лежит в диапазоне [min, max], и функция проверки
check(x)меняется монотонно (false -> true).
Шаблон 1: Стандартный (Поиск точного значения)
let l = 0, r = nums.length - 1;
while (l <= r) {
const mid = l + Math.floor((r - l) / 2); // Избегаем переполнения
if (nums[mid] === target) return mid;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;Шаблон 2: Поиск границы (Min Feasible / Lower Bound)
Задача: Найти первое число, удовлетворяющее условию (например, Bad Version).
let l = 0, r = maxVal; // Диапазон поиска ответа
let ans = -1;
while (l <= r) {
const mid = l + Math.floor((r - l) / 2);
if (check(mid)) {
ans = mid; // Возможно это ответ, но может есть левее?
r = mid - 1; // Пробуем уменьшить
} else {
l = mid + 1; // Слишком мало, увеличиваем
}
}
return ans;