Функция bsearch () в C ++ выполняет двоичный поиск элемента в массиве элементов и возвращает указатель на элемент, если он найден.
Функция bsearch () требует, чтобы в массиве выполнялся поиск всех элементов, меньших, чем элемент, находящийся слева от него.
Точно так же все элементы, которые больше искомого, должны находиться справа от него в массиве. Это требование выполняется, если массив отсортирован по возрастанию.
bsearch () прототип
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* compare) (const void *, const void *));
Функция определена в заголовочном файле.
Функция bsearch () ищет ключ в базе массива. Все элементы, меньшие чем key, должны стоять перед ним в базе массива. Точно так же все элементы больше, чем key, должны появляться после него в базе.
Для выполнения поиска функция bsearch () выполняет серию вызовов функции, на которую указывает compare с ключом в качестве первого аргумента и элементом из массива в качестве второго аргумента.
Параметры bsearch ()
- ключ: указатель на элемент для поиска
- base: указатель на первый элемент массива
- num: номер элемента в массиве
- size: Размер в байтах каждого элемента в массиве
- compare: указатель на функцию, сравнивающую два элемента. Он возвращается
- отрицательное целое число, если первый аргумент меньше второго
- положительное целое число, если первый аргумент больше второго
- ноль, если оба аргумента равны
key передается как первый аргумент, а элемент из массива передается как второй аргумент. Прототип функции сравнения выглядит так:
int compare (const void * a, const void * b);
bsearch () Возвращаемое значение
Функция bsearch () возвращает:
- Указатель на найденный элемент. Если найдено более одного совпадающего элемента, то не указано, адрес какого элемента функция вернет в качестве результата.
- Нулевой указатель, если элемент не найден.
Пример 1: Как работает функция bsearch ()?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (5,9,10,14,16,19,21,26,29,31); int key1 = 10; int *p1 = (int*)bsearch(&key1,arr,num,sizeof(int),compare); if(p1 == NULL) cout << key1 << " not found " << endl; else cout << key1 << " found at position " << (p1-arr) << endl; int key2 = 15; int *p2 = (int*)bsearch(&key2,arr,num,sizeof(int),compare); if(p2 == NULL) cout << key2 << " not found " << endl; else cout << key2 << " found at position " << (p2-arr) << endl; return 0; )
Когда вы запустите программу, вывод будет:
10 найдено в позиции 2 15 не найдено
Пример 2: Как функция bsearch () работает более чем с одним совпадающим элементом?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (2,3,5,7,8,10,14,14,14,15); int key = 14; int *p = (int*)bsearch(&key,arr,num,sizeof(int),compare); if(p == NULL) cout << key << " not found " << endl; else /* 14 occurs at position 6,7 and 8*/ cout << key << " found at position " << (p-arr) << endl; return 0; )
Когда вы запустите программу, возможный результат будет:
14 находится в позиции 7
