bsearch

Статья
06/09/2015

Выполняет бинарный поиск в сортированном массиве. Существует более безопасная версия этой функции; см. раздел bsearch_s.

void *bsearch( 
   const void *key,
   const void *base,
   size_t num,
   size_t width,
   int ( __cdecl *compare ) (const void *key, const void *datum) 
);

Параметры

key
Искомый объект.
base
Указатель на начало данных для поиска.
num
Количество элементов.
width
Ширина элементов.
compare
Функция обратного вызова, которая сравнивает два элемента. Первый параметр - указатель на ключ для поиска, а второй - указатель на элемент массива для сравнения с ключом.

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

bsearch возвращает указатель на вхождение key в массив, на который указывает base. Если key не найден, функция возвращает NULL. Если массив не отсортирован по возрастанию или содержит повторяющиеся записи с одинаковыми ключами, невозможно точно предсказать результат.

Заметки

Функция bsearch выполняет бинарный поиск по отсортированному массиву, состоящему из num элементов, каждый размером width байт. Значение base — указатель на начало массива, в котором должен производиться поиск, а key — искомое значение. Параметр compare — указатель предоставляемую пользователем процедуру, которая сравнивает требуемый ключ с элементом массива и возвращает одно из следующих значений, отражающих их связь:

Значение, возвращаемое процедурой compare	Описание
< 0	Ключ меньше, чем элемент массива.
0	Ключ равен элементу массива.
> 0	Ключ больше, чем элемент массива.

Эта функция проверяет свои параметры. Если compare, key или num имеют значение NULL, или если base имеет значение NULL, и *num отлично от нуля, или если width равно нулю, вызывается обработчик недопустимого параметра, как описано в разделе Проверка параметров. Если продолжение выполнения разрешено, то errno устанавливается в EINVAL и функция возвращает NULL.

Требования

Подпрограмма	Обязательный заголовок
bsearch	<stdlib.h> и <search.h>

Дополнительные сведения о совместимости см. в разделе Совместимость во введении.

Пример

Программа сортирует массива строк с помощью qsort, а затем использует bsearch, чтобы обнаружить ключевое слово «cat».

// crt_bsearch.c
#include <search.h>
#include <string.h>
#include <stdio.h>

int compare( char **arg1, char **arg2 )
{
   /* Compare all of both strings: */
   return _strcmpi( *arg1, *arg2 );
}

int main( void )
{
   char *arr[] = {"dog", "pig", "horse", "cat", "human", "rat", "cow", "goat"};
   char **result;
   char *key = "cat";
   int i;

   /* Sort using Quicksort algorithm: */
   qsort( (void *)arr, sizeof(arr)/sizeof(arr[0]), sizeof( char * ), (int (*)(const 
   void*, const void*))compare );

   for( i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i )    /* Output sorted list */
      printf( "%s ", arr[i] );

   /* Find the word "cat" using a binary search algorithm: */
   result = (char **)bsearch( (char *) &key, (char *)arr, sizeof(arr)/sizeof(arr[0]),
                              sizeof( char * ), (int (*)(const void*, const void*))compare );
   if( result )
      printf( "\n%s found at %Fp\n", *result, result );
   else
      printf( "\nCat not found!\n" );
}