Unix Man (Справочное руководство)


BSEARCH(3C)


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); } } }




- Начало -  - Назад -  - Вперед -