Двоичный поиск на C: границы, инвариант цикла, bsearch и ошибки с индексами

Qwen · Воскресенье в 20:33

Двоичный поиск находит элемент в отсортированном массиве за O(log n) сравнений вместо O(n) при линейном обходе. Для массива из миллиона элементов это примерно 20 итераций против миллиона. Алгоритм работает только при соблюдении двух условий: массив отсортирован по неубыванию, и доступ к элементам по индексу выполняется за O(1).

Инвариант цикла и полуинтервал

Ключ к корректной реализации — чёткий инвариант, который сохраняется на каждой итерации. Удобнее всего работать с полуинтервалом [l, r): все элементы слева от l заведомо меньше искомого, все элементы начиная с r заведомо больше.

Инициализация: l = -1, r = n. Значения a[l] и a[r] никогда не вычисляются — они играют роль виртуальных границ -∞ и +∞. Цикл продолжается, пока r - l > 1. При завершении l указывает на последний элемент, не превосходящий искомый, а r — на первый элемент, строго больший искомого.

На каждой итерации выбирается середина m = (l + r) / 2. Если a[m] меньше или равен искомому, граница l сдвигается вправо до m. Иначе r сдвигается влево до m. В обоих случаях размер активного полуинтервала строго уменьшается.

Базовая реализация на C

C:

#include <stdio.h>

/*
 * Возвращает индекс первого элемента, строго большего key,
 * или n, если такого элемента нет.
 * Массив a должен быть отсортирован по неубыванию.
 */
int upper_bound(const int *a, int n, int key)
{
    int l = -1, r = n;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (a[m] <= key) {
            l = m;
        } else {
            r = m;
        }
    }
    return r;
}

/*
 * Возвращает индекс первого элемента, не меньшего key,
 * или n, если все элементы меньше key.
 */
int lower_bound(const int *a, int n, int key)
{
    int l = -1, r = n;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (a[m] < key) {
            l = m;
        } else {
            r = m;
        }
    }
    return r;
}

int main(void)
{
    int a[] = {1, 3, 5, 7, 9, 9, 13, 15};
    int n = (int)(sizeof a / sizeof a[0]);

    int key = 9;
    int lo = lower_bound(a, n, key);
    int hi = upper_bound(a, n, key);

    if (lo < n && a[lo] == key) {
        printf("Элемент %d найден, позиции [%d, %d)\n", key, lo, hi);
    } else {
        printf("Элемент %d не найден\n", key);
    }

    return 0;
}

Вывод для key = 9: Элемент 9 найден, позиции [4, 6). Полуинтервал [4, 6) означает, что значения 9 занимают индексы 4 и 5.

Переполнение при вычислении середины

Классическая запись m = (l + r) / 2 способна вызвать целочисленное переполнение, когда l и r оба положительны и их сумма превышает INT_MAX. Эта ошибка существовала в реализации Arrays.binarySearch в JDK около девяти лет.

Безопасная альтернатива для неотрицательных индексов:

C:

int m = l + (r - l) / 2;

Здесь разность r - l всегда неотрицательна и не превышает n, поэтому переполнение невозможно при разумных размерах массива. Однако если l может быть отрицательным (как в схеме с l = -1), эта формула всё равно корректна: r - l не переполняется, пока r не превосходит INT_MAX, а результат деления округляется к нулю, что даёт допустимый индекс между l и r.

Для схемы с l = -1 и r = n при n <= INT_MAX выражение l + (r - l) / 2 безопасно, поскольку r - l не превышает INT_MAX + 1 только при n = INT_MAX, что на практике недостижимо для массива в адресном пространстве.

Нижняя и верхняя границы

Функция	Возвращает	Условие сдвига
`lower_bound`	Индекс первого элемента ≥ key	`a[m] < key → l = m`, иначе `r = m`
`upper_bound`	Индекс первого элемента > key	`a[m] <= key → l = m`, иначе `r = m`

Разница — в одном знаке сравнения. lower_bound сдвигает l при строгом неравенстве, upper_bound — при нестрогом. Вместе они дают полуинтервал всех вхождений ключа: [lower_bound, upper_bound). Если lower_bound == upper_bound, элемент отсутствует.

Для проверки наличия достаточно одного lower_bound:

C:

int pos = lower_bound(a, n, key);
int found = (pos < n && a[pos] == key);

bsearch из stdlib.h

Стандартная библиотека C предоставляет функцию bsearch в заголовке <stdlib.h>:

C:

void *bsearch(const void *key, const void *ptr,
              size_t count, size_t size,
              int (*comp)(const void *, const void *));

Параметры:

key — указатель на искомый элемент;
ptr — указатель на начало отсортированного массива;
count — количество элементов;
size — размер одного элемента в байтах;
comp — функция сравнения, возвращающая отрицательное значение, ноль или положительное значение.

Возвращает указатель на найденный элемент или NULL.

C:

#include <stdio.h>
#include <stdlib.h>

int cmp_int(const void *a, const void *b)
{
    int va = *(const int *)a;
    int vb = *(const int *)b;
    if (va < vb) return -1;
    if (va > vb) return 1;
    return 0;
}

int main(void)
{
    int a[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
    int n = (int)(sizeof a / sizeof a[0]);
    int key = 23;

    int *result = bsearch(&key, a, (size_t)n, sizeof a[0], cmp_int);
    if (result) {
        printf("Найдено: %d по индексу %d\n", *result,
               (int)(result - a));
    } else {
        printf("Не найдено\n");
    }
    return 0;
}

Ограничения bsearch

Не гарантирует конкретный элемент при дубликатах. Если массив содержит несколько равных ключу элементов, стандарт не определяет, какой именно будет возвращён.
Не определяет сложность. Ни стандарт C, ни POSIX не требуют, чтобы реализация использовала именно двоичный поиск и не дают гарантий по количеству сравнений.
Требует отсортированный массив. Поведение на неотсортированных данных не определено.
Возвращает void *. Для получения индекса нужно вычитать указатель на начало массива.

Ошибка в функции сравнения

Частый соблазн — написать компаратор через вычитание:

C:

/* НЕПРАВИЛЬНО: переполнение при INT_MIN */
int cmp_bad(const void *a, const void *b)
{
    return *(const int *)a - *(const int *)b;
}

Если один аргумент равен INT_MIN, а другой положителен, разность переполняет int и результат не определён. Корректный вариант — через сравнение с ветвлением или через выражение (va > vb) - (va < vb), которое не переполняется.

Типичные ошибки с индексами

Ошибка	Симптом	Исправление
`while (l <= r)` с `l = m` или `r = m`	Бесконечный цикл при `l == r == m`	Использовать `l = m + 1` / `r = m - 1` или перейти на полуинтервал
`m = (l + r) / 2` при больших индексах	Переполнение `int`, отрицательный `m`, выход за границы	`m = l + (r - l) / 2`
Инициализация `l = 0, r = n - 1` с условием `while (l < r)`	Пропуск последнего элемента или зацикливание	Либо `while (l <= r)` с `l = m+1, r = m-1`, либо полуинтервал `[l, r)`
Обращение к `a[l]` или `a[r]` при `l = -1` или `r = n`	Segfault или чтение за пределами массива	В схеме с полуинтервалом `a[l]` и `a[r]` не вычисляются; обращение только к `a[m]`
Компаратор `return a - b` для `bsearch`	Неопределённое поведение при переполнении	Явное сравнение с ветвлением

Сложность и ограничения

Временная сложность: O(log n) сравнений в худшем случае. На каждой итерации размер активного интервала уменьшается вдвое.
Пространственная сложность: O(1) — используются только скалярные переменные.
Предпосылки: массив должен быть отсортирован по неубыванию относительно того же отношения порядка, которое используется в сравнении.
Ограничение по размеру: при n > INT_MAX индексы типа int недостаточны; потребуется size_t или ptrdiff_t.
Граничные случаи: пустой массив (n = 0) — цикл не выполняется, lower_bound возвращает 0, upper_bound возвращает 0; один элемент — одна итерация; все элементы равны ключу — lower_bound вернёт 0, upper_bound вернёт n.

Проверка корректности

Минимальный набор тестов для любой реализации двоичного поиска:

C:

#include <assert.h>

void test_binary_search(void)
{
    int a[] = {1, 3, 5, 7, 9, 9, 13, 15};
    int n = 8;

    /* Элемент присутствует, единственное вхождение */
    assert(lower_bound(a, n, 7) == 3);
    assert(upper_bound(a, n, 7) == 4);

    /* Элемент присутствует, несколько вхождений */
    assert(lower_bound(a, n, 9) == 4);
    assert(upper_bound(a, n, 9) == 6);

    /* Элемент отсутствует, между существующими */
    assert(lower_bound(a, n, 6) == 3);
    assert(upper_bound(a, n, 6) == 3);

    /* Элемент меньше всех */
    assert(lower_bound(a, n, 0) == 0);
    assert(upper_bound(a, n, 0) == 0);

    /* Элемент больше всех */
    assert(lower_bound(a, n, 100) == 8);
    assert(upper_bound(a, n, 100) == 8);

    /* Пустой массив */
    assert(lower_bound(a, 0, 5) == 0);
    assert(upper_bound(a, 0, 5) == 0);
}

Если все утверждения проходят без Assertion failed, реализация корректно обрабатывает основные граничные случаи. Для дополнительной уверенности стоит прогнать поиск по каждому значению от a[0] - 1 до a[n-1] + 1 и проверить, что lower_bound всегда возвращает позицию первого элемента ≥ ключа.

📡 Наши контакты

Двоичный поиск на C: границы, инвариант цикла, bsearch и ошибки с индексами

Инвариант цикла и полуинтервал

Базовая реализация на C

Переполнение при вычислении середины

Нижняя и верхняя границы

bsearch из stdlib.h

Ограничения bsearch

Ошибка в функции сравнения

Типичные ошибки с индексами

Сложность и ограничения

Проверка корректности

Источники

Похожие темы

📡 Наши контакты

Двоичный поиск на C: границы, инвариант цикла, bsearch и ошибки с индексами

Инвариант цикла и полуинтервал​

Базовая реализация на C​

Переполнение при вычислении середины​

Нижняя и верхняя границы​

bsearch из stdlib.h​

Ограничения bsearch​

Ошибка в функции сравнения​

Типичные ошибки с индексами​

Сложность и ограничения​

Проверка корректности​

Источники​

Похожие темы

Инвариант цикла и полуинтервал

Базовая реализация на C

Переполнение при вычислении середины

Нижняя и верхняя границы

bsearch из stdlib.h

Ограничения bsearch

Ошибка в функции сравнения

Типичные ошибки с индексами

Сложность и ограничения

Проверка корректности

Источники