Бинарный поиск (массив)

O(log n)

Делим пространство поиска пополам на каждом шаге по отсортированным данным: сравниваем со средним элементом и отбрасываем половину, где ответа быть не может.

Сигналы

отсортированный массивнайти цель / первое или последнее вхождениеn до 1e6+ и ожидается O(log n)найти границу, где условие меняетсяпоиск во вращённом, но почти отсортированном массиве (с подвохом)

Шаблон

function binarySearch(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Похоже, но не то

Линейный поиск: Бинарный поиск нужен только когда данные реально отсортированы и n достаточно велико, чтобы O(log n) имело значение. На неотсортированных данных или при малом n сортировка обойдётся дороже, чем линейный проход.
Бинарный поиск во вращённом массиве: Обычный бинарный поиск считает, что весь массив отсортирован слева направо. Вращённый массив это нарушает: сначала нужно понять, какая половина ещё отсортирована, и только потом отбрасывать одну из них.

отсортированный массив, n до 1e6+, нужна скорость быстрее O(n) -> O(log n) время, O(1) память. Отсортированность плюс большое n - сигнал сюда; без сортировки бинарный поиск не работает.

Изучить этот паттерн