Функција бсеарцх () у Ц ++-у врши бинарно претраживање елемента у низу елемената и враћа показивач на елемент ако је пронађен.
Функција бсеарцх () захтева да се сви елементи мање од елемента претражују лево од њега у низу.
Исто тако, сви елементи већи од елемента за претрагу морају бити десно од њега у низу. Овај захтев је испуњен ако је низ сортиран у растућем редоследу.
прототип бсеарцх ()
воид * бсеарцх (цонст воид * кеи, цонст воид * басе, сизе_т нум, сизе_т сизе, инт (* упореди) (цонст воид *, цонст воид *));
Функција је дефинисана у датотеци заглавља.
Функција бсеарцх () тражи кључ у основи низа. Сви елементи мање од кључа морају се појавити пре њега у бази низа. Исто тако, сви елементи већи од кључа морају се појавити након њега у бази.
Да би извршила претрагу, функција бсеарцх () врши низ позива функцији на коју је указано упоређивање са кеи као првим аргументом и елементом из низа као другим аргументом.
бсеарцх () параметри
- тастер: показивач на елемент за претрагу
- база: Показивач на први елемент низа
- нум: Број елемента у низу
- величина: Величина у бајтовима сваког елемента у низу
- упореди: Показивач на функцију која упоређује два елемента. Враћа се
- негативан цео број ако је први аргумент мањи од другог
- позитиван цео број ако је први аргумент већи од другог
- нула ако су оба аргумента једнака
Кључ се преноси као први аргумент, а елемент из низа као други аргумент. Прототип функције упоређивања изгледа:
инт упореди (цонст воид * а, цонст воид * б);
бсеарцх () Повратна вредност
Функција бсеарцх () враћа:
- Показивач на пронађени елемент. Ако се пронађе више подударних елемената, тада није одређено која ће адреса елемента функција вратити као резултат.
- Нулти показивач ако елемент није пронађен.
Пример 1: Како функционише функција бсеарцх ()?
#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: Како функција бсеарцх () ради за више од једног одговарајућег елемента?
#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