bsearch()

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

Прототип:

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

Аргументы:

key

Объект для поиска.

base

Указатель на первый элемент массива.

nmemb

Количество элементов в массиве.

size

Размер элемента в байтах.

compare

Указатель на пользовательскую функцию, которая вызывается для сравнения элемента массива с key. Аргументы функции сравнения:

• pkey — тот же указатель, что и key
• pbase — указатель на элемент в массиве.

Функция сравнения должна возвращать целое число, меньшее, равное или большее нуля, если объект key меньше, равен или больше элемента в массиве.

Библиотека:

libc

Описание:

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

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

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

---

Если имеется несколько совпадающих элементов в массиве, который соответствует 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

Безопасность использования

Точка остановки потока

Нет

Обработчик прерываний

Да

Обработчик сигналов

Да

В потоке

Да

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

hsearch(), lfind(), lsearch(), qsort(), tsearch()

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