Namespaces
Variants

bsearch, bsearch_s

From cppreference.net
C
Algorithms
(C11)
bsearch bsearch_s
(C11)
Определено в заголовочном файле <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 , и следующие ошибки обнаруживаются во время выполнения и вызывают текущую установленную constraint handler функцию:
  • count или size больше RSIZE_MAX
  • key , ptr или comp является нулевым указателем (если только 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) устарели.

(since C23)

Содержание

Параметры

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

Сигнатура функции сравнения должна быть эквивалентна следующей:

int cmp ( const void * a, const void * b ) ;

Функция не должна изменять переданные ей объекты и должна возвращать согласованные результаты при вызове для одних и тех же объектов, независимо от их позиций в массиве.

​

context - состояние компаратора (например, последовательность сортировки), передается в comp в качестве третьего аргумента

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

1) Указатель на элемент в массиве, который сравнивается как равный * key , или нулевой указатель, если такой элемент не найден.
2) То же, что и (1) , за исключением того, что нулевой указатель также возвращается при нарушениях ограничений времени выполнения.
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

Смотрите также

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