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

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

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

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

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

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

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

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

Источники: Википедия: Двоичный поиск, Документация Python (англ.): bisect

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 binarySearch(arr: number[], target: number): number {
    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;
}

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

function binarySearch(array $arr, $target) {
    $lo = 0; $hi = count($arr) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) $lo = $mid + 1;
        else $hi = $mid - 1;
    }
    return -1;
}

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

    public static int BinarySearch(int[] arr, int target) {
        int lo = 0, hi = arr.Length - 1;
        while (lo <= hi) {
            int mid = (int)(((uint)(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)». Решение на нём обычно укладывается в O(log n).

• •отсортированный массив
• •найти цель / первое или последнее вхождение
• •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).