I got this problem in an interview. I thought my solution was right but the interviewer said I was not using the sorted property of the array. I can see that I am using the standard binary search here but I am not able to understand why this does not provide the optimum solution.
/*
Write a function to return if an element is part of sorted rotated array
*/
bool findInt(int arr[],int val, int size){
cout<<"Inside findInt"<<endl;
int start,end,mid;
start=0;
end=size-1;
mid = (end-start)/2;
while(start<=end){
cout<<"start:"<<start<<",mid:"<<mid<<",end:"<<end<<endl;
if(arr[mid]==val) returntrue;
if(val>=arr[start] && val<arr[mid]){
end=mid-1;
mid = start+((end-start)/2);
}
else{
start=mid+1;
mid = start+((end-start)/2);
}
}
returnfalse;
}
if(val>=arr[start] && val<arr[mid])
Because of the rotated property, `val' may be greater than `arr[start]' and `arr[mid]'.
In that case, the condition will fail and you would end searching in the wrong portion of the array.