• Binary Search is a searching algorithm which is used to quickly find a value in a sorted sequence of elements.

  • It uses divide and conquer strategy to find the element.

  • It is an efficient search algorithm as compared to linear search.

  • Elements must be sorted in order to use Binary Search.

  • We will divide the search space (array) in two parts using variables:

    1. start - initially 0.
    2. mid
    3. end - initially n-1 where n is number of elements of the array
  • Calculate mid = (start + end)/2

  • Check if the element at mid is equal to the element we are looking for, if yes then element found.

  • If not, then check if element we are looking for is greater than (>) or less than (<) the element at mid.

    1. If greater: start = mid+1
    2. If less: end = mid - 1
  • Repeat steps 6,7,8 untill we find the element or start becomes greater than end which is the exit condition i.e. we will loop untill start <= end

  • Suppose in the example we are looking for element 8.

  • Element 8 found at index 5.

# Source Code - C++

#include <iostream>
using namespace std;

//Function to perform Binary Search
int BinarySearch (int A[], int n, int e)
int start, end, mid;
start = 0;
end = n-1;
 while( start <= end )
  mid = (start + end)/2;
  if( A[mid] == e)
   return mid;
  if( e > A[mid])
  else  if( e < A[mid])
  end = mid-1;
return -1;

//Main Function
int main() {

 int n;
 cout<<"enter size of array\n";
 int A[n],e,i,ans;
 cout<<"enter elements of array\n";
 cout<<"enter element to be found\n";
 cout<<"not found\n";
 cout<<"Found at index:"<<ans;
 return 0;

Time Complexity: O(log n)

Learn More

  • Binary Search