Точный бинарный поиск через инвариант

В [1,3,5,7,9] при поиске 7 середина сначала равна 5: левая половина отбрасывается, следующая середина равна 7, ответ — индекс 3.

Как найти точное значение в отсортированном массиве?

Найти индекс target в отсортированном массиве или вернуть -1.

Линейный просмотр до совпадения

Просмотреть элементы слева направо до совпадения за O(n).

Почему порядок должен позволить отбрасывать половину?

Линейный поиск не использует порядок и отбрасывает только один элемент за сравнение.

Середина доказывает бесполезность одной стороны

Сравнение с серединой доказывает, в какой половине target не может находиться.

Где может оставаться target в начале итерации?

В начале каждой итерации, если target присутствует, хотя бы одно его вхождение находится в закрытом диапазоне [lo,hi].

Сужаем закрытый диапазон [lo, hi]

Пока lo <= hi, вычислить mid = lo + (hi-lo)/2. При равенстве вернуть mid; если значение меньше target, сделать lo=mid+1, иначе hi=mid-1.

Точный бинарный поиск на C++17 и Python 3

C++17

#include <cassert>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& values, int target) {
    int lo = 0;
    int hi = static_cast<int>(values.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    assert(binarySearch({1, 3, 5, 7, 9}, 7) == 3);
    assert(binarySearch({1, 3, 5}, 2) == -1);
    assert(binarySearch({}, 2) == -1);
}

Python 3

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


assert binary_search([1, 3, 5, 7, 9], 7) == 3
assert binary_search([1, 3, 5], 2) == -1
assert binary_search([], 2) == -1

Сколько раз можно делить диапазон пополам?

O(log n) времени и O(1) памяти: длина диапазона хотя бы вдвое уменьшается. Вход обязан быть отсортирован по тому же порядку сравнения.

Пустой массив, крайние индексы и безопасный mid

Пустой массив даёт hi=-1; один элемент; target на концах; дубликаты — возвращается любое вхождение; большие индексы.

Тесты на найденный и отсутствующий target

[],5 -> -1, [4],4 -> 0, [1,3,5],1/5, отсутствующий 2, массив с дубликатами.

Когда условие обещает отсортированность?

Данные отсортированы и нужно найти точное значение за логарифмическое число сравнений.

Когда бинарный поиск неприменим к данным?

На неотсортированных данных или при дорогом случайном доступе (обычный linked list) эта реализация не подходит.

Мини-проверка: почему lo становится mid + 1?

Вопрос: почему при a[mid] < target можно убрать и mid? Ответ: mid не равен target, а все позиции левее имеют не большее значение.

Мини-проверка: зачем вычислять mid через разность границ?

Вопрос: зачем mid = lo + (hi-lo)/2? Ответ: это избегает сложения двух потенциально больших индексов.

Проследите границы при поиске 7

Проследите поиск 7 в [1,3,5,7,9,11], записывая lo, hi, mid и исключённую половину.

Найдите значение двоичным поиском самостоятельно

Задача 1

Найдите target в отсортированном по убыванию массиве или верните -1, самостоятельно выбрав и обосновав направления сдвига.

Инвариант оправдывает каждое отбрасывание половины

Смысл бинарного поиска — не формула середины, а доказательство, что отброшенная половина не содержит ответа.