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 less 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 greater 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 revbinsearch(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 revbinsearch(x,middle+1,r,a);
else if(x>a[middle])
return revbinsearch(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=revbinsearch(x,0,n-1,a); //return the index of x in a[]
cout<<ans;
return 0;
}
INPUT:
10
20 17 15 14 13 10 9 7 5 4
9
OUTPUT:
6
0 Comments