# Binary Search

• 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;
  else
  if( e > A[mid])
  start=mid+1;
  else  if( e < A[mid])
  end = mid-1;
 }
return -1;
}

//Main Function
int main() {

 int n;
 cout<<"enter size of array\n";
 cin>>n;
 int A[n],e,i,ans;
 cout<<"enter elements of array\n";
 for(i=0;i<n;i++)
 cin>>A[i];
 cout<<"enter element to be found\n";
 cin>>e;
 ans=BinarySearch(A,n,e);
 if(ans==-1)
 cout<<"not found\n";
 else
 cout<<"Found at index:"<<ans;
 return 0;
}

Time Complexity: O(log n)