BSEARCH(3C)
НАЗВАНИЕ
bsearch - бинарный поиск в отсортированной таблице
СИНТАКСИС
#include <search.h>
char *bsearch ((char *) key, (char *) base, nel, sizeof (*key), compar)
unsigned nel;
int (*compar) ( );
ОПИСАНИЕ
Функция bsearch предназначена для выполнения бинарного
поиска в соответствии с алгоритмом, описанным в книге
Д. Кнута: Искусство программирования для ЭВМ. Т. 3.
Сортировка, поиск. - М.: Мир, 1978. Раздел 6.2.1, алгоритм B.
Функция bsearch возвращает указатель внутрь таблицы на
искомые данные. Предварительно таблица должна быть отсортирована в возрастающем порядке согласно предоставленной функции сравнения. Аргумент key указывает на
об ект данных, разыскиваемый в таблице (ключ поиска);
base указывает на первый элемент таблицы; nel задает
количество элементов в таблице; compar - это функция
сравнения, аргументами которой при вызове служат два
указателя на сравниваемые элементы. В соответствии с
тем, какое целое число она возвращает: меньшее нуля,
равное нулю или большее нуля, первый аргумент считается
меньшим, равным или большим по отношению ко второму.
ПРИМЕР
Следующий пример демонстрирует поиск в таблице, содержащей указатели на узлы, которые состоят из цепочек
символов и их длин. Таблица отсортирована в алфавитном
порядке по цепочкам символов в узлах.
Приведем фрагмент программы, который считывает цепочку
символов и ищет соответствующий узел, затем распечатывает цепочку символов с ее длиной или выводит сообщение
об ошибке.
#include <stdio.h>
#include <search.h>
#define TABSIZE 1000
struct node { /* Структура узлов */
char *string;
int length;
};
struct node table [TABSIZE]; /* Таблица для поиска */
...
{
struct node *node_ptr, node;
int node_compare (); /* Функция сравнения узлов */
char str_space [20]; /* Пространство для ввода цепочки
символов */
...
node.string = str_space;
while (scanf ("%s", node.string) != EOF) {
node_ptr =
(struct node *) bsearch ((char *) (&node),
(char *) table, TABSIZE,
sizeof (struct node), node_compare);
if (node_ptr != NULL) {
(void) printf ("string = %20s, length = %d\n",
node_ptr->string, node_ptr->length);
} else {
(void) printf ("not found:%s\n", node.string);
}
}
}
/*
Следующая функция сравнивает два узла по цепочкам
символов на основе алфавитного порядка
*/
int node_compare (node1, node2)
char *node1, *node2;
{
return strcmp (((struct node *) node1) -> string,
((struct node *) node2) -> string);
}
ПРИМЕЧАНИЯ
Указатели на ключ (key) и на первый элемент таблицы
(base) должны иметь тип "указатель на элемент" и преобразовываться к типу "указатель на символ".
В сравнении, осуществляемом функцией compar, не обязательно должен участвовать каждый байт, поэтому элементы
таблицы в дополнение к сравниваемым величинам могут содержать произвольные данные.
Хотя функция bsearch описывается как имеющая тип "указатель на символ", возвращаемое ею значение следует
преобразовывать к типу "указатель на элемент".
СМ. ТАКЖЕ
hsearch(3C), lsearch(3C), qsort(3C), tsearch(3C).
ДИАГНОСТИКА
В случае неудачного поиска результатом служит пустой
указатель NULL