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);
       |    }          
       |  }          
       |} 
                                                               
       |/*   
       |  Следующая функция сравнивает два узла по цепочкам
       |  символов на основе алфавитного порядка
       |*/                            
       |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.