Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Modification of binary search. I assume there is no duplicates in array.
int rotatedBinarySearch(int A[], int N, int key) {
int L = 0;
int R = N - 1;
while (L <= R) {
int M = L + ((R - L) / 2);
if (A[M] == key)
return M;
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}
Refer to leetcode.
There shouldn't be any duplicates in the array.
The below java code would work fine
public static int findElement(int[] a, int low, int high, int x)
{
while(low<=high)
{
int mid=(low+high)/2;
if(a[mid]==x)
return mid;
else if(a[mid]<=a[high]){
if(x>a[mid]&&x<a[high])
low=mid+1;
else
high=mid-1;
}
else
{
if(x<a[mid]&&x>a[low])
high=mid-1;
else
low=mid+1;
}
}
return -1;
}
There shouldn't be any duplicates in the array.
The below java code would work fine
public static int findElement(int[] a, int low, int high, int x)
{
while(low<=high)
{
int mid=(low+high)/2;
if(a[mid]==x)
return mid;
else if(a[mid]<=a[high]){
if(x>a[mid]&&x<a[high])
low=mid+1;
else
high=mid-1;
}
else
{
if(x<a[mid]&&x>a[low])
high=mid-1;
else
low=mid+1;
}
}
return -1;
}
#include <iostream>
using namespace std;
int testarray[20]={26,27,28,29,30,32,36,40,45,50,4,5,7,9,10,15,18,20,22,25};
int binary_search(int x, int start, int last)
{
if(testarray[start]==x)return start;
else if(testarray[last]==x)return last;
else
{
int middle =(start+last)/2;
if(start==middle) return -1;
if(x>testarray[middle])
return binary_search(x,middle,last);
else
return binary_search(x,start,middle);
}
}
int find(int x,int start, int last)
{
if(testarray[start]!=x && testarray[last]!=x)
{
int middle=(start+last)/2;
if(testarray[middle]==x)
return middle;
if(testarray[middle]<testarray[start] && testarray[middle]<x)
return binary_search(x,middle,last);
else if(testarray[middle]>testarray[start] && testarray[start]<x)
return binary_search(x,start,middle);
else if(testarray[middle]<testarray[start] && testarray[middle]>x)
return find(x,start,middle);
else if(testarray[middle]>testarray[start])
return find(x,middle,last);
else
cout<<"not found";
return -1;
}
else
{
if(testarray[start]==x)return start;
else return last;
}
}
int main() {
// your code goes here
int x,start=0,last=19;
cout<<"enter element you wanna search \n ";
cin>>x;
int pos=find(x,start,last);
cout<<pos;
cin>>x;
return 0;
}
Modification of binary search
int checkKey (int s, int e, int mid, int a[], int key)
{
if (a[s] == key)
return s;
if (a[e] == key)
return e;
if (a[mid] == key)
return mid;
return -1;
}
int find (int a[], int s, int e, int k)
{
if (s > e)
return -1;
int mid = s + (e -s)/2;
int i = checkKey (s, e, mid, a, k);
if (i != -1)
return i;
if (s == e || mid == s)
return -1;
if (k > a[mid])
s = mid+1;
else
e = mid-1;
return find (a,s,e,k);
}
- Coder January 12, 2014