C++ bsearch()

The bsearch() function requires all elements less than the element to be searched to the left of it in the array.

Likewise, all elements greater than the element to be searched must be to the right of it in the array. This requirement is fulfilled if the array is sorted in ascending order.

bsearch() prototype

void* bsearch (const void* key, const void* base, size_t num, size_t size, int (*compare)(const void*,const void*));

The function is defined in <cstdlib> header file.

The bsearch() function searches for key in the array base. All elements less than key must appear before it in the array base. Likewise, all elements greater than key must appear after it in base.

In order to perform the search, the bsearch() function makes a series of calls to the function pointed by compare with key as the first argument and an element from the array as the second argument.

bsearch() Parameters

• key: Pointer to the element to search
• base: Pointer to the first element of the array
• num: Number of element in the array
• size: Size in bytes of each element in the array
• compare: A pointer to a function that that compares two elements. It returns
  • a negative integer if the first argument is less than the second
  • a positive integer if the first argument is greater than the second
  • zero if both arguments are equal

key is passed as the first argument and an element from the array is passed as the second argument. The prototype of the comparison function looks like:

int compare(const void* a, const void* b);

bsearch() Return value

The bsearch() function returns:

• Pointer to the found element. If more than one matching elements are found, then it is unspecified which element's address the function will return as the result.
• Null pointer if the element is not found.

Example 1 : How bsearch() function works?

#include <iostream>
#include <cstdlib>
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;
}

When you run the program, the output will be:

10 found at position 2
15 not found

Example 2 : How bsearch() function works for more than one matching elements?

#include <iostream>
#include <cstdlib>
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;
}

When you run the program, a possible output will be:

14 found at position 7