PROBLEM STATEMENT:
You are given an array which sorted but rotated in clockwise direction. You have to find an element in this array.
QUICK POINTS:
1. We can find the index of the minimum element as explained in the previous post.
2. This minimum index will divide the array in two sorted parts and so we can apply binary search in both the parts to find the element.
ALGORITHM:
1. Find the middle element.
2. If the middle element is greater than the next element, then the index of minimum element will be mid+1 (see the example, if we can find 20 as the middle element, then 1 is the minimum element).
3. If the middle index is strictly greater than the left index and the middle element is less than the previous element, then the index of minimum element will be middle index. ( See in the example, if 1 is middle element, 20 is greater than 1, so 1 is the minimum element.
4. If middle element is less than the right most element, search in the left part of the middle index.
5. If middle element is greater than left element, search in the right part of the middle index.
6. Now, you can apply binary search on both the parts i.e. left and right with respect to the index of the minimum element.
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 minelement(int l,int r, int a[])
{ if(l>r)
return 0;
if(l==r)
return l;
if(r>=l)
{
int mid=l+(r-l)/2;
if(mid<r && a[mid]>a[mid+1])
return mid+1;
if(mid>l && a[mid]<a[mid-1])
return mid;
if(a[mid]<a[r])
return minelement(l,mid-1,a);
if(a[mid]>a[l])
return minelement(mid+1,r,a);
}
}
int main()
{
int n,x; //size of array
cin>>n>>x;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans=minelement(0,n-1,a);
int u=binsearch(x,0,ans-1,a);
int v=binsearch(x,ans,n-1,a);
if(u!=-1)
cout<<u;
else if(v!=-1)
cout<<v;
else
cout<<"DOESN'T EXIST";
return 0;
}
INPUT:
10 3
17 18 20 1 3 4 5 6 10 15
OUTPUT:
4
0 Comments