C++ Tutorials

C++ Tutorials

Binary Search: Search a sorted array by repeatedly dividing the search interval in half using C++.

#include<bits/stdc++.h>
#include<iostream>
#include<climits>

using namespace std;

int bs(int arr[], int n, int key){
  int start =0;
  int end=n-1;
  while(start <= end){
    int mid ((start + end)/2);

    if(arr[mid]==key){
      return mid;
    }
    else if(arr[mid] > key){
      end = mid - 1;
    }
    else{
      start=mid+1;
    }
  }
return -1;
}

int main(){


int n, key, i;
cout<<"Enter number of array: ";
cin>>n;
int arr[n];
for(i=0; i<=n; i++){
  cout<< "Enter "<<i+1<<" number of element: ";
  cin>>arr[i];
}
cout<<"Enter element you want to search: ";
cin>>key;
cout<<bs(arr,n,key)<<endl;



return 0 ;
}

Binary Search is a searching algorithm which is used to quickly find a value in a sorted sequence of elements and it uses divide and conquer strategy to find the element. Binary Search is an efficient search algorithm as compared to linear search because when we look at the time complexity of linear search which is O(n) where ‘n’ is the number of elements, the time complexity of binary search is O(log n) which is way faster than linear search.

So now lets try to understand how binary search works. Suppose this is the array given to us and we are looking for the element 8, So the basic steps that we will follow to perform binary search are : firstly we can only perform binary search when the collection of elements given to us is sorted and as we can see the example that we have taken is sorted in ascending order,

Next, we will divide the search space i.e. the array in two parts using the variables ‘mid’, ‘start’ and ‘end’ where we initialize ‘start’ as zero and ‘end’ as n-1 where n is the number of elements in the array, So in-short we are storing first index in the variable ‘start’ and the last index of the array in variable ‘end’.

Next, we will calculate the middle index using the ‘start’ and ‘end’ variables and store it in the variable ‘mid’ which would be equal to (start + end)/2 and then we will check the element at the middle index whether it is the element we are looking for, if it is not we will check if the value of the element we are looking for is greater than or less than the value of the element at middle index and if the value is greater then we will store the index mid+1 in ‘start’ else if the value is less we will store the index mid-1 in ‘end’ and we will repeat the steps 5,6,7,8,9, until we find the element we are looking for.

So let’s implement this to understand what we are actually doing. Firstly we initialise the variable ‘start’ to 0 i.e. it has the index of the first element and we store the index n-1 that in our case is 10 -1 which is 9 in the variable ‘end’, so our variable ‘end’ has the index 9 and using the formula to calculate the middle index which would be (0 + 9)/2 which would be 4 as we are only considering the integer value and we are not concerned with the decimal part, so this means that our variable ‘mid’ has the index 4.

So now we can see using the variables ‘start’ ‘mid’ and ‘end’ we have divided our array into two sub-arrays that is from index 0 to 4 and index 5 to 9. In the next step, we will check the value of the element at the middle index which is equal to 7, but we are looking for the element 8, so in the next step we will check if the value of the element we are looking for is greater than or less than the value at the middle index.

Now as 8 is greater than 7 in the next iteration we will make ‘start = mid + 1’ that is 4+1 which is 5 which means that start has the index of element 8 and there will be no change in the value of ‘end’. Now as we have made start equal to mid+1 this means that now we will be searching in the sub-array 5 to 9 and we are sure that the element we are looking for is not present in the sub-array 0 to 4 because the value of the element is greater than 7, So in this way we have reduced our search space by half and now again calculating the value of ‘mid’ which would now be (5 + 9)/2 which is equal to 7, therefore, mid now has the index 7.

Now we again check the value at middle index which is not equal to 8 and by comparison 8 is smaller than 12, therefore in the next iteration the value of ‘start’ would remain the same and we will make ‘end’ equal to mid-1 that is 6, therefore we have again reduced our search space by half and now we will again calculate the value of mid which would be (5 +6)/2 that is 5.

Therefore, ‘mid’ now has the index 5 and now the value at the middle index is equal to 8 which is the element we were looking for, therefore we simply say that the element 8 is present at index 5 which is stored in the ‘mid’ variable. Therefore with three iterations, we were able to find the element 8 which in linear search would take 6 iterations from index 0 to 5.

Now one last case is if the element we are looking for is not present in the array that we will have the exit condition that ‘start’ is greater than ‘end’ which means that we will search until ‘start’ is less than or equal to ‘end’, taking an example to suppose instead of 8 we were looking for element 10 which is not present in the array then in the next iteration as 10 is greater than 8 so we will make the value of ‘start’ as mid+1 which is equal to 6 and there would be no change in the value of ‘end’ and again reducing the search space by half and calculating the value of ‘mid’ which is equal to (6 + 6)/2 that is 6 and now if we check the value at ‘mid’ it is equal to 9 which is not the value we are looking for and as 10 is greater than 9 we are required to make the value of ‘start’ as mid+1 which would be 7 and we already know that the element we are looking for will not be present at that index. Therefore we will look for the element while ‘start’ is less than or equal to ‘end’.

So now let’s quickly implement this using C++. We define our binary search function which takes as arguments an integer array ‘A’, integer ‘n’ which is the number of elements in the array, and an integer ‘e’ which is the element we are looking for and our function returns the index of the element if it is present in the array, otherwise, it returns -1.

So firstly we declare our three variables ‘start’, ‘end’, and ‘mid’. We initialize ‘start’ to 0 and ‘end’ with n-1, next we start our while loop with the condition that we will perform a binary search while ‘start’ is less than or equal to ‘end’, and then we store the value (start + end)/2 in the variable ‘mid’ which is the middle index and if the value at middle index is equal to the element we are looking for we simply return ‘mid’ which would be the index of that element, otherwise we check if the value of the element we are looking for is greater than the value of the element at ‘mid’ then we make ‘start’ equal to mid+1 else if the value of ‘e’ is less than the value of the element at ‘mid’ we make ‘end’ equal to mid-1 and we repeat these steps until we find the element we are looking for or the value of ‘start’ becomes greater than the value of ‘end’ which means that the element is not present in the array and in that case we return -1.