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

Бинарный поиск (массив): как это работает?

Держите две границы, низ и верх, на отсортированном отрезке. Ответ, если он есть, лежит между ними.

Возьмите средний индекс этого отрезка. Сравните стоящее там значение с искомым.

При совпадении поиск закончен. Верните этот индекс.

Если среднее значение мало, цель лежит правее. Сдвиньте низ за середину.

Если оно велико, сдвиньте верх левее середины. В обоих случаях половина отрезка исчезает.

Цикл кончается, когда низ обогнал верх. Отрезок пуст, значит цели нет.

1. lo=0 hi=5Ищем 7 в [1, 3, 5, 7, 9, 11]. Кандидатов шесть.
2. mid=2, значение 55 меньше 7. Всё левее выбывает.
3. lo=3 hi=5, mid=4, значение 99 больше 7. Всё правее выбывает.
4. lo=3 hi=3, mid=3, значение 7Остался один кандидат, и он подходит.
5. возврат 3Три сравнения на шесть элементов. Удвоение входа добавит одно.

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;
}

Бинарный поиск (массив): разбор примера

Первая и последняя позиция значения

В отсортированном массиве одно значение может повторяться много раз. Верните первый и последний индекс цели.

Если значения нет, верните минус один дважды.

Запустите поиск дважды с разным правилом при совпадении.

Для первого индекса после совпадения двигайте верх влево. Для последнего двигайте низ вправо.

function searchRange(nums, target) {
    function bound(findFirst) {
        let lo = 0;
        let hi = nums.length - 1;
        let found = -1;

        while (lo <= hi) {
            const mid = lo + Math.floor((hi - lo) / 2); // cannot overflow

            if (nums[mid] === target) {
                found = mid;
                // a match is not the end: keep squeezing the chosen side
                if (findFirst) hi = mid - 1;
                else lo = mid + 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return found;
    }

    return [bound(true), bound(false)];
}

Бинарный поиск (массив): когда применять?

Эти формулировки в условии ведут сюда:

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

Бинарный поиск (массив): с чем путают?

• Линейный поиск (Linear search): Перебор читает каждый элемент, но порядка не требует. Бинарному поиску порядок нужен, зато он читает log n.
• Бинарный поиск во вращённом массиве (Binary search on a rotated array): Поворот рвёт единый отсортированный кусок. Проверка сначала ищет отсортированную половину.
• Бинарный поиск по ответу (Binary search on the answer): Там отрезок это множество возможных ответов, а не массив. Проверку вы пишете сами.
• Двоичное дерево поиска (Binary search tree): Дерево делит пополам так же, но через указатели. Ещё оно допускает вставки, чего массив не умеет.
• Два указателя (с концов) (Two pointers (opposite ends)): Там двигаются оба конца, и проверяемая пара меняется. Здесь за шаг двигается одна граница.

Бинарный поиск (массив): частые ошибки

• Считают mid как lo плюс hi пополам

  Такая сумма может выйти за безопасный диапазон. Пишите lo плюс половина разрыва.

• Двигают границу в mid, а не за него

  Отрезок перестаёт сжиматься, и цикл не кончается. Берите mid плюс один или mid минус один.

• Смешивают два вида цикла

  При lo <= hi обе границы входят в отрезок. Смена одной границы без другой ломает инвариант.

• Ищут в неотсортированных данных

  Сравнение считает, что слева от mid всё меньше. Без этого ответ тихо неверен.

Бинарный поиск (массив): задачи с собеседований

• Бинарный поиск: Чистая форма на различных отсортированных значениях.
• Позиция для вставки: Верните место, куда значение встало бы, если его нет.
• Первая и последняя позиция элемента: Два поиска с противоположным правилом при совпадении.
• Поиск пика: Сравнение идёт с соседом, а не с целью.
• Квадратный корень: Отрезок это множество ответов, а не массив.
• Поиск в двумерной матрице: Считайте всю сетку одним отсортированным списком.
• Наименьшая буква больше заданной: Верхняя граница, которая заворачивается к началу.

Бинарный поиск (массив): сложность по времени и памяти

O(log n)

n до 1e9 нормально, потому что log2 от 1e9 около 30. Время O(log n), память O(1).