Функцията bsearch () в C ++ извършва двоично търсене на елемент в масив от елементи и връща указател към елемента, ако бъде намерен.
Функцията bsearch () изисква всички елементи, по-малки от елемента, да бъдат търсени вляво от него в масива.
По същия начин всички елементи, по-големи от търсения елемент, трябва да бъдат вдясно от него в масива. Това изискване е изпълнено, ако масивът е сортиран във възходящ ред.
bsearch () прототип
void * bsearch (const void * ключ, const void * base, size_t num, size_t size, int (* сравнение) (const void *, const void *));
Функцията е дефинирана в заглавния файл.
Функцията bsearch () търси ключ в основата на масива. Всички елементи, по-малки от ключ, трябва да се появят пред него в основата на масива. По същия начин всички елементи, по-големи от ключ, трябва да се появят след него в базата.
За да извърши търсенето, функцията bsearch () прави поредица от извиквания на функцията, посочена чрез сравнение с key като първи аргумент и елемент от масива като втори аргумент.
bsearch () Параметри
- ключ: указател към елемента за търсене
- основа: указател към първия елемент от масива
- num: Номер на елемента в масива
- size: Размер в байтове на всеки елемент в масива
- сравни: указател към функция, която сравнява два елемента. Връща се
- отрицателно цяло число, ако първият аргумент е по-малък от втория
- положително цяло число, ако първият аргумент е по-голям от втория
- нула, ако и двата аргумента са равни
ключ се предава като първи аргумент, а елемент от масива се предава като втори аргумент. Прототипът на функцията за сравнение изглежда така:
int сравнение (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
