Функция bsearch

Прототип функции bsearch:

void * bsearch( const void * searchkey, const void * baseptr, size_t number, size_t size, int ( * funccompar ) ( const void *, const void * ) );

Описание

Функция bsearch выполняет двоичный поиск в массиве.
Алгоритм поиска запрашивает искомое значение, которое передается через параметр searchkey, в массиве, на который ссылается  указатель baseptr. Количество элементов массива передается через параметр number, каждый элемент массива имеет размер size байт. В конце, функция возвращает указатель void * на первое вхождение искомого значения.

Для выполнения поиска, функция сравнивает элементы с искомым элементом, путем вызова функции  через параметр *comparator, указанного в качестве последнего аргумента.

Потому как эта функция выполняет алгоритм бинарного поиска, все значения в массиве baseptr должны быть  отсортированы в порядке возрастания, с теми же критериями, которые использует функция  funccompar.

Параметры:

• searchkey
  Указатель на искомый объект типа void*.
• baseptr
  Указатель на первый элемент массива, в котором будет выполняться поиск, типа void*.
• number
  Количество элементов массива base.
• size
  Размер каждого элемента массива base в байтах.
• funccompa
  Функция для сравнения двух элементов массива. Функция должна иметь следующий прототип:

int funccompar( const void * searchkey, const void * cmpelem );

Функция должна принимать два параметра: первый указывает на искомый объект, а второй — на один из элементов массива, типа void *. Функция должна привести передаваемые параметры к нужным типам данных и выполнить сравнение.
Возвращаемое значение этой функции неоднозначно. Если сравниваемый элемент с искомым значением меньше, равен или больше, функция должна вернуть, отрицательное значение, ноль или положительное значение, соответственно.
Для основных типов данных, которые поддерживают регулярные выражения, функция сравнения может выглядеть так:

int funccompar (const void * key, const void * cmpelem)
{
  if ( *(type*)key >  *(type*)cmpelem ) return 1;
  if ( *(type*)key == *(type*)cmpelem ) return 0;
  if ( *(type*)key <  *(type*)cmpelem ) return -1;
}

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

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

Пример: исходный код программы

//пример использования функции bsearch
#include <iostream>
#include <cstdlib>

int funccmp(const void * x1, const void * x2)                            // функция сравнения
{
  return ( *(int*)x1 - *(int*)x2 );                                           // если результат вычитания - 0, значит числа равны
}

int values[] = { 10, 20, 25, 40, 90, 100 };                                 // отсортированный массив

int main()
{

  int key = 40;                                                             // искомый элемент массива
  int * ptrItem = (int*) bsearch(&key, values, 6, sizeof (int), funccmp);

  if (ptrItem != NULL)
    std::cout <<  "Число " << *ptrItem << " находится в массивеn";
  else
    std::cout <<   "Числа " << key << " в массиве нетn";
  return 0;
}

Пример работы программы

В примере есть массив отсортированных целых чисел. Существует также функция funccmp, которая сравнивает два значения передаваемых через параметры x1 и x2, и возвращает результат вычитания значений. Если результат  0 — значения равны, положительный результат — сравниваемое значение меньше, отрицательный результат  — сравниваемое значение больше.

В main вызывается функция bsearch для поиска в массиве values значение  40. Как только искомое значение найдено, программа выводит его на экран, смотреть пример работы программы ниже.

Для Си-строк функция strcmp может быть использована в качестве последнего аргумента функции bsearch.

Пример: исходный код программы

//пример использования функции bsearch, для поиска строки в массиве строк
#include <iostream>
#include <cstdlib>
#include <cstring>

char arraystr[][20] = {"галактика", "млечный", "путь", "вселенная", "космос"};             // массив строк

int main()
{
    char key[20] = "путь";

    // сортируем строки в массиве
    qsort (arraystr, 5, 20, (int(*)(const void*, const void*)) strcmp);

    std::cout << "Отсортированный массив строк:n";
    for (int ix = 0; ix < 5; ix++)
        std::cout << arraystr[ix] << "  ";

    // поиск строки
    char * ptrItem = (char*) bsearch(key, arraystr, 5, 20, (int(*)(const void*,const void*)) strcmp);

    if (ptrItem!=NULL)
      std::cout << "nnСтрока "" << ptrItem << "" есть в массивеn";
    else
      std::cout << "nnСтроки "" << key << "" в массиве нетn";
    return 0;
}

Пример работы программы