bsearch, bsearch_s

Определено в заголовке `<stdlib.h>`
void* bsearch( const void key, const void ptr, size_t count, size_t size, int (comp)(const void, const void*) );	(1)
void* bsearch_s( const void key, const void ptr, rsize_t count, rsize_t size, int (comp)(const void , const void , void ), void *context );	(2)	(с C11)
/QVoid/* bsearch( const void key, /QVoid/ ptr, size_t count, size_t size, int (comp)(const void, const void*) );	(3)	(с C23)
/QVoid/* bsearch_s( const void key, /QVoid/ ptr, rsize_t count, rsize_t size, int (comp)(const void , const void , void ), void *context );	(4)	(с C23)

1) Ищет элемент, равный элементу, на который указывает key в массиве, на который указывает ptr. Массив содержит count элементов по size байт и должен быть упорядочен относительно key, то есть все элементы, сравниваемые как меньшие, должны предшествовать всем элементам, сравниваемым как равные, а те, в свою очередь, должны предшествовать всем элементам, сравниваемым как большие, чем ключевой объект. Полностью отсортированный массив удовлетворяет этим требованиям. Элементы сравниваются с помощью функции, на которую указывает comp. Поведение не определено, если массив не был предварительно упорядочен относительно *key в порядке возрастания согласно тому же критерию, что и comp.

2) Аналогично (1), за исключением того, что дополнительный аргумент состояния context передается в comp и что следующие ошибки обнаруживаются во время выполнения и вызывают текущую установленную функцию обработчика ограничений обработчика ограничений:

count или size больше, чем RSIZE_MAX
key, ptr или comp является указателем null (если только count не равно нулю)

Как и во всех функциях с проверкой границ, bsearch_s (и соответствующий тип-обобщённый макрос)(с C23) гарантированно доступен только если __STDC_LIB_EXT1__ определено реализацией, и если пользователь определил __STDC_WANT_LIB_EXT1__ как целочисленную константу 1 до включения <stdlib.h>.

3,4) Тип-обобщенные макросы, эквивалентные (1) и (2) соответственно. Пусть T — это неквалифицированный тип объекта (включая void).

Если ptr имеет тип const T*, тип возврата — const void*.
В противном случае, если ptr имеет тип T*, тип возврата — void*.
В противном случае поведение не определено.

Если определение макроса каждой из этих универсальных функций подавлено для доступа к фактической функции (например, если используется (bsearch), (bsearch_s), или указатель на функцию), становится видна фактическая декларация функции (1) или (2).

Если массив содержит несколько элементов, которые comp указывали бы как равные искомому элементу, то не определено, какой элемент функция вернет в качестве результата.

Прямое использование фактических функций (1) и (2) устарело.

(с C23)

Параметры

key	-	указатель на элемент для поиска
ptr	-	указатель на массив для проверки
count	-	количество элементов в массиве
size	-	размер каждого элемента в массиве в байтах
comp	-	функция сравнения, которая возвращает отрицательное целое значение, если первый аргумент меньше второго, положительное целое значение, если первый аргумент больше второго, и ноль, если аргументы эквивалентны. `key` передаётся в качестве первого аргумента, а элемент из массива — как второй. Подпись функции сравнения должна быть эквивалентна следующей: int cmp(const void a, const void b); Функция не должна изменять передаваемые ей объекты и должна возвращать согласованные результаты при вызове для одних и тех же объектов, независимо от их положения в массиве.
context	-	состояние компаратора (например, последовательность сортировки), передаваемое в `comp` в качестве третьего аргумента

Возвращаемое значение

1) Указатель на элемент в массиве, который сравнивается как равный *key, или указатель null, если такой элемент не был найден.

2) Аналогично (1), за исключением того, что указатель null также возвращается при нарушениях ограничений во время выполнения.

3,4) Аналогично (1) и (2) соответственно, за исключением того, что квалификация cv-типа корректируется.

Примечания

Несмотря на название, ни стандарты C, ни POSIX не требуют от этой функции реализации с использованием бинарного поиска или гарантий сложности.

В отличие от других функций с проверкой границ, bsearch_s не обрабатывает массивы нулевого размера как нарушение ограничения во время выполнения, а вместо этого указывает, что элемент не найден (другая функция, которая принимает массивы нулевого размера, — это qsort_s).

До bsearch_s, пользователи bsearch часто использовали глобальные переменные для представления состояния компаратора.

Пример

#include <stdlib.h>
#include <stdio.h>
 
struct data {
    int nr;
    char const *value;
} dat[] = {
    {1, "Foo"}, {2, "Bar"}, {3, "Hello"}, {4, "World"}
};
 
int data_cmp(void const *lhs, void const *rhs) 
{
    struct data const *const l = lhs;
    struct data const *const r = rhs;
 
    if (l->nr < r->nr) return -1;
    else if (l->nr > r->nr) return 1;
    else return 0;
 
    // return (l->nr > r->nr) - (l->nr < r->nr); // possible shortcut
    // return l->nr - r->nr; // erroneous shortcut (fails if INT_MIN is present)
}
 
int main(void) 
{
    struct data key = { .nr = 3 };
    struct data const *res = bsearch(&key, dat, sizeof dat / sizeof dat[0],
                                     sizeof dat[0], data_cmp);
    if (res) {
        printf("No %d: %s\n", res->nr, res->value);
    } else {
        printf("No %d not found\n", key.nr);
    }
}

Вывод:

No 3: Hello

Ссылки

Стандарт C17 (ISO/IEC 9899:2018):

7.22.5.1 Функция bsearch (с. 258)
K.3.6.3.1 Функция bsearch_s (с. 441-442)

Стандарт C11 (ISO/IEC 9899:2011):

7.22.5.1 Функция bsearch (с. 355)
K.3.6.3.1 Функция bsearch_s (с. 608-609)

Стандарт C99 (ISO/IEC 9899:1999):

7.20.5.1 Функция bsearch (с. 318-319)

Стандарт C89/C90 (ISO/IEC 9899:1990):

4.10.5.1 Функция bsearch

См. также

qsortqsort_s (C11)	сортирует диапазон элементов неуказанного типа (функция)
C++ документация для `bsearch`

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/c/algorithm/bsearch