bsearch()

Выполнить бинарный поиск в сортированном массиве

Прототип:

#include <stdlib.h>
void *bsearch( const void *key,
const void *base,
size_t num,
size_t width,
int (*compar)( const void *pkey,
const void *pbase ) );

Аргументы:

key
Объект для поиска.
base
Указатель на первый элемент массива.
num
Количество элементов в массиве.
width
Размер элемента в байтах.
compare
Указатель на пользовательскую функцию, которую lfind() вызывает для сравнения элемента массива с key. Аргументы функции сравнения: Функция сравнения должна возвращать целое число, меньшее, равное или большее нуля, если объект key меньше, равен или больше элемента в массиве.

Библиотека:

libc

Описание:

Функция bsearch() выполняет двоичный поиск в отсортированном массиве из num объектов (на начальный элемент его, размером width, указывает аргумент base) элемент, совпадающий с объектом, обозначенным key.

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

Функция bsearch() возвращает указатель на соответствующий элемент массива или NULL, если совпадений не найдено.


Note: Если имеется несколько совпадающих элементов в массиве, который соответствует key, то возвращаемый указатель не определен.

Примеры:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static const char *keywords[] = {
"auto",
"break",
"case",
"char",
/* ... */
"while"
};
#define NUM_KW sizeof( keywords ) / sizeof( char * )
int kw_compare( const void *p1, const void *p2 )
{
const char *p1c = (const char *) p1;
const char **p2c = (const char **) p2;
return (strcmp( p1c, *p2c ));
}
int keyword_lookup( const char *name )
{
const char **key;
key = (char const **) bsearch( name, keywords, NUM_KW,
sizeof( char * ), kw_compare );
if ( key == NULL )
return (-1);
return (key - keywords);
}
int main( void )
{
printf( "%d\n", keyword_lookup( "case" ) );
printf( "%d\n", keyword_lookup( "crigger" ) );
printf( "%d\n", keyword_lookup( "auto" ) );
return (EXIT_SUCCESS);
}

Код генерирует следующий вывод:

$ ./a.out 2 -1 0

Классификация:

ANSI, POSIX 1003.1

Точка остановки потока
Нет
Обработчик прерываний
Да
Обработчик сигналов
Да
В потоке
Да

Тематические ссылки:

lfind(), lsearch(), qsort()




Предыдущий раздел: Описание API системной библиотеки