Amazon Interview Question
Software Engineer / DevelopersNo need for two binary searches
You already know the end of the array i.e A[k-1] (0- based index)
SO check if X<A[0]
if yes then do binary search for no on array from A[k] to A[n]
else do binary search on array from a[0] to A[k-1]
if X=A[0] return obviously
worst case would be o(logn) if k==n
The below code is for finding min_element. The same logic applies for searching too, compare mid with element to b found and check which intervals to search for.
int Solve() {
int i,j;
int n;
GI(n);
int A[n];
REP(i,n) GI(A[i]);
int ret = Find_Min(A,0,n-1);
sort(A,A+n);
cout<<ret<<"\t"<<A[0]<<endl;
if(ret==A[0]) cout<<"you are a stud :)\n";
else cout<<"you are terrible :(\n";
return 0;
}
int Find_Min(int A[],int start,int end) {
if(start<=end) {
if(start==end) return A[start];
int mid = (start+end)/2;
if(A[mid]>A[end]) return Find_Min(A,mid+1,end);
if(A[mid]<A[start]) return Find_Min(A,start,end-1);
if(A[mid]==A[start]) return A[mid];
}
}
Only one pass of binary search without knowing k
public static int binarySearch(int[] arr, int value){
int low =0;
int high = arr.length-1;
while(low <= high){
int mid = (low + high)/2;
if(arr[mid] == value){
return mid;
}else if(arr[mid] > value){
if(arr[high] > arr[mid] || arr[high] < value){
high = mid -1;
}else{
low = mid + 1;
}
}else{
if(arr[low] <= arr[mid] || arr[low] > value){
low = mid + 1;
}else{
high = mid - 1;
}
}
}
return -1;
}
I believe a two pass binary search would work, the first pass to find the starting of the array and the second pass to do the actual search by shifting the start, mid and end values with respect to the newly found start index.
- Robben May 24, 2010First pass :
while(start<end)
{
mid=start+(end-start)/2;
if(a[mid]<a[start])
end=mid;
else
start=mid
}
This code will give you the index of the last element of the original array. Let this value be stored in variable 'correct'.
Second Pass:
Follow binary search algo and at each iteration correct the start, end and mid values to start+correct,mid+correct and end+correct. If these values exceed length of array then subtract the value from length.