Функція 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
