Binary search is an efficient approach of searching an element from a sorted list of items. It works by repeatedly dividing the list in two equal parts, considering the part which contains the element in each step.
Binary search is applied when the question gives a list that is already sorted.
ALGORITHM:
Suppose, we are to x in a sorted list of n items. Binary search works as follows:
1. Find the middle element of the list.
2. Compare x with the middle element. If x is equal to the middle element, then we return the position of x as the index of the middle element.
If x is greater than the middle element, then x will lie in the right part of the middle element, and we will consider the right part as our list for next step.
If x is less than the middle element, then x will lie in the left part of the middle element, and we will consider the left part as our list for next step.
3. The same steps are continued until we find a list consisting of only one element and that is equal to x.
CODE:
#include <bits/stdc++.h>
using namespace std;
int binsearch(int x,int l,int r,int a[])
{
if(r>=l){
int middle=l+(r-l)/2;
if(x==a[middle])
return middle;
else if(x>a[middle])
return binsearch(x,middle+1,r,a);
else if(x<a[middle])
return binsearch(x,l,middle-1,a);
}
return -1; //if the element doesn't exist
}
int main()
{
int n; //size of array
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int x;
cin>>x; //element to be searched
int ans=binsearch(x,0,n-1,a);//return the index of x in a[]
cout<<ans;
return 0;
}
INPUT:
10
1 4 7 9 11 12 14 15 16 20
7
OUTPUT:
2
MOST COMMON QUESTIONS RELATED TO BINARY SEARCH
HOW TO APPLY BINARY SEARCH ON REVERSE SORTED ARRAY?
HOW TO FIND FIRST AND LAST OCCURRENCE OF AN ELEMENT IN A LIST?
HOW TO FIND NUMBER OF OCCURRENCE OF AN ELEMENT IN AN ARRAY?
HOW MANY TIMES A SORTED ARRAY IS ROTATED TO GET ANOTHER ARRAY?
HOW TO FIND AN ELEMENT IN A SORTED ROTATED ARRAY?
HOW TO PERFORM SEARCHING OPERATION IN A NEARLY SORTED ARRAY?
HOW TO FIND THE NEXT NEAREST LETTER OF A CHARACTER PRESENT IN A SORTED CHARACTER ARRAY?
HOW TO FIND POSITION OF AN ELEMENT IN AN INFINITE SORTED ARRAY?
0 Comments