Binary Search in CPP using Divide and Conquer Algorithm

In this CPP tutorial, we are going to discuss the binary search algorithm using Divide and Conquer paradigm in C++

Binary search in C++ with Divide and Conquer Algorithm

This tutorial will focus on Binary search in C++. Let’s understand the basics of divide and conquer first. Then we will go for binary search step by step. Hope this will be useful to the learners.

What is Divide and Conquer Algorithm?

Divide and Conquer algorithm divides a given problem into subproblems of the same type and recursively solve these subproblems and finally combine the result.

Read also,

What is Binary Search Algorithm?

Binary search works for a sorted array. In a sorted array, it searches for a key element in a given array. It compares the key value with the middle value if it matches with the middle value it returns true otherwise it compares the key value with middle value if it is greater than middle value than left half of sub-array is of no use and we check only for the right half of sub-array. Otherwise, it goes for the left half of sub-array and this procedure reoccurs until we do not get middle element as key element or size of reduced sub-array becomes 1.

So, in binary search algorithm we are dividing the given problem i.e. checking for key value in whole array into subproblems by reducing size of array half recursively.




CPP code implementation of Binary_search in C++

#include<bits/stdc++.h>

  using namespace std;

   int Binary_search(int arr[],int l,int r, int key)
 
  {
       if(l<=r)
     {
         int mid = l+((r-l)/2);
         
         if(arr[mid]==key)
          return 1;
          
          else if(arr[mid]>key)
           return Binary_search(arr,l,mid-1,key);
           
           else
             return Binary_search(arr,mid+1,r,key);
     }
     
     return 0;
 }

   int main()
 {
   int arr[]={3,4,5,6,7,8,4,5,2,8,9,13,14,17,19};
   
   int n=sizeof(arr)/sizeof(arr[0]);
   
    int key=79;
   
   sort(arr,arr+n);
   
    if(Binary_search(arr,0,n-1,key))
     cout<<"key is found in given array"<<endl;
     
     else
      cout<<"key is not found in given array"<<endl;
 }

here, first, we sort the given array as:

2 3 4 4 5 5 6 7 8 8 9 13 14 17 19

then, we first check for the middle element which is 7 and our key is 79 so, key>arr[mid]

we check for array mid+1 to n-1 we repeat the same procedure of dividing the array into half until we do not reach the single element of the array in divided sub-array or key is found.

 

 

Time Complexity

T(n) = T(n/2) + c

the solution for above reoccurrence is Theta( Logn )

STL Method to implement binary-search

binary_search ( arr, arr+n, key)

where key is the value to be searched in array arr.

 


Leave a Reply

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