std::bsearch in C++ with examples

In this tutorial we will learn about std::bsearch function and how it works in C++. As the name suggests, it stands for binary search.

We will explain how binary method of searching works generally. Then we will finally dive into the specifics of how we can work with the function itself.

std::bsearch in C++

The algorithm:

If we want to find out the position of an element in an array, a very natural approach is that we scan through the list of elements in O(n) and find out where the element is. If our application requires you find the position of a SORTED array, we can make use of that fact and employ binary search algorithm. It uses divide and conquer strategy to finish the task in O(logn) worst case.

Making use of the fact that the array is sorted, we check if the element to be found is present in the middle. If not, we know that since the array is sorted. The element if greater than the mid element has to be present to the right of the mid element. If it’s smaller it has to be on the left. We reduce our search area by half each time and keep checking the mid element in each sub-array using the same strategy.

We can implement this ourselves but C++ has one already implemented which we can make use of.

std::bsearch()

This function takes five arguments. They are:

  1. key: The element that needs to be found
  2. ptr: pointer to the first element of the array, basically passing the array
  3. arr-len: The number of elements in the array
  4. size: The size of the elements in the array in bytes
  5. cmp: function which takes to elements as arguments and returns -1 if the second one is larger, 1 if the first one is larger and 0 if they are equal.

Here, we have the implementation of bsearch and cmp function that compares. First, we get the number of elements the array and the element to be searched from the user. We, then store them.

The function bsearch will return a pointer. We need to catch the return pointer and therefore store it in myptr. We pass the required arguments as stated above.

The cmp function is pretty simple in that it returns a negative, positive integer or 0 if the first element is bigger, smaller or equal respectively.

Below is the code for the same.

#include <iostream>
#include <stdio.h>
#include <cstdlib>
using namespace std;

int cmp(const void* num1, const void* num2)
{
  const int* a = (int*) num1;
  const int* b = (int*) num2;
  return (*a - *b);
}

int main()
{
    
  int size;
  cout<<"Enter the number of elements"<<endl;
  cin>>size;
  int array[size];
  cout<<"Enter the elements"<<endl;
  for(int i=0; i<size; i++){
      cin>>array[i];
  }
  int key;
  cout<<endl;
  cout<<"Enter the element to be searched"<<endl;
  cin>>key;
  int *myptr = (int*)bsearch(&key,array,size,sizeof(int),cmp);

  if(myptr == NULL)
    cout << key << " is not present in the array " << endl;
  else
    cout << key << " is present at index " << (myptr-array) << endl;

  return 0;
}

Output:

Enter the number of elements                                                                                                    

8                                                                                                                               

Enter the elements                                                                                                              

4 5 6 7 8 9 10 100                                                                                                              

                                                                                                                                

Enter the element to be searched                                                                                                

9                                                                                                                               

9 is present at index 5

binary_search() is function that performs a similar binary search. Keep Learning!

That is the end of the tutorial on std::bsearch.

Also read: Find kth smallest element in a Binary Search tree in C++

Leave a Reply

Your email address will not be published. Required fields are marked *