Amazon Interview Question
SDE-2sTeam: Bangalore
Country: India
Interview Type: In-Person
It is possible! You need to apply binary search twice in that case. See my algorithm below.
@avahuasca-if you search in both the subarrays for many cases,its o(n) not o(logn).
binary search is O(logn) search because in each iteration if reduce length by half.
will you say the following prog is also o(logn)?
int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}
no this is o(n) only..correct me if I am wrong
@amit
You are right! My solution below does not work - I missed thinking about some fundamental use-cases before proposing a solution. Sorry about that!
I believe time complexity of Amit's Solution is O(logn/2) + O(logn/2) not O(n) as binary search is performed on half of original array 2 times.
int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}
@anonymous--this is normal search(although not linear),not binary search..you may try in an unsorted array
Optimization:
int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
if((a[mid]<a[high]) && key > a[mid])// in this case
//our pivot and key will always occur after a[mid]
//searching in left subArray is waste
return search(a,mid+1,high,key);
if((a[mid]<a[high]) && key < a[mid])// in this case
//our pivot will always occur after a[mid]
//key will occur before a[mid]
//a[low] to a[mid] is just increasing subArray
return search(a,low,mid-1,key);
return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}
same as two more cases:
if((a[mid]<a[low]) && key > a[mid])// in this case
//our pivot and key will always occur before a[mid]
//searching in right subArray is waste
return search(a,low.mid,key);
if((a[mid]<a[low]) && key < a[mid])// in this case
//our pivot will always occur before a[mid]
//key will occur after a[mid]
//a[mid] to a[high] is uniform decreasing order
Regarding complexity even in worst case we are not touching all elements n......
As we are using binary search two times it looks like complexity is:
O(log [n / constant1] ) + O(log [n / constant2] )
in case pure increasing or decreasing order array
O(log n)
in all other cases:
O(log [n / constant1] ) + O(log [n / constant2] )
where
constant1 = 2+ {2,3,4....}
constant2 = 2+ {2,3,4....}
let us consider the reading as reading of some curve.. according to the given data first part has +ve slop and second part has negative slop.(i.e a[i+1]-a[i] is +ve for first half and -ve for second half) to find the pivot in log(n) complexity first consider start_point and end_point element then find mid_point (start_point+end_point)/2 find its slop if it is +ve replace start_point with mid element if -ve replace end_point with mid_point repeat the procedure updating start_point and end_point finally you end up with a pivot point(with log(n) complexity). once pivot is found perform binary search again worst case complexity is log(n). overall complexity is 2log(n) or O(log(n))
by making some modification in above method we can search for an element. that is once the slop of mid_point is checked if that is + ve check whether key is between start_point and mid_point if it is in between then key found if not we found that key is not in increasing part... it should be in decreasing part... same applies for decreasing part also... once the key not found we can repeat the dividing part till we get the key in between other part of the list... the complexity is still O(log(n))...
We can try with this one.
1) First check the element that joins both increasing and decreasing array using binary search(logn).
2) then search the key in the left subarray using binary search(logn).
3) If it is not present in left subarray, search it in right subarray using binary search(logn).
We will have to use different methods for these operations.
Correct me if I am wrong.
We need to determine the inversion first ...
This can be done in o(log n) and decide from there which side array we must search.
Eg. {1,7,10,12,25,30,27,20)
The inversion is 30,27 position is 5 . It can be found in O(log(n))
Do a binary search (which has conditions reversed ) on the right side to determine the position of the key O(log(n))
if not found
Do a binary search on the left side of the key to determine the position of the key O(log(n)).
Pivot is different from locating inversion. I think , please correct me if i m wrong
static bool searchElement(int[] array, int first, int end, int start, int finish, int element)
{
if (first <= end)
{
int mid = (first + end) / 2;
int midright = mid + 1;
int midleft = mid - 1;
if (midleft < first)
midleft = first;
if (midright > end)
midright = end;
if (array[midleft] <= array[mid] && array[mid] <= array[midright])
{
if (element < array[mid])
{
if (mid - 1 >= first)
return searchElement(array, first, mid - 1, start, finish, element);
else
return searchElement(array, (start + finish) / 2, finish, (start + finish) / 2, finish, element);
}
else
{
if (element > array[mid])
{
if (mid + 1 <= end)
return searchElement(array, mid + 1, end, start, finish, element);
else
return searchElement(array, (start + finish) / 2, finish, (start + finish) / 2, finish, element);
}
else
{
if (array[mid] == element)
return true;
else
return false;
}
}
}
else
{
if (array[midleft] >= array[mid] && array[mid] >= array[midright])
{
if (element < array[mid])
{
if (mid + 1 <= end)
return searchElement(array, mid + 1, end, start, finish, element);
else
return searchElement(array, start, (start + finish) / 2, start, (start + finish) / 2, element);
}
else
{
if (element > array[mid])
{
if (mid - 1 >= first)
return searchElement(array, start, mid - 1, start, finish, element);
else
return searchElement(array, start, (start + finish) / 2, start, (start + finish) / 2, element);
}
else
{
if (array[mid] == element)
return true;
else
return false;
}
}
}
else
{
if (element == array[mid])
return true;
else
return (searchElement(array, first, mid - 1, start, finish, element) ||
searchElement(array,mid+1,end,start,finish,element));
}
}
}
return false;
}
import java.io.*;
public class RotatedArray {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] A = new int[N];
for(int i = 0; i < N; ++i)
A[i] = Integer.parseInt(br.readLine());
int K = Integer.parseInt(br.readLine());
int start = 0;
int end = N-1;
while(start <= end) {
int mid = start+(end-start)/2;
if(A[mid] == K) {
System.out.println(mid);
break;
}
else {
if(A[end] < A[mid]) {
if(K < A[mid]) {
start = mid+1;
}
else {
end = mid-1;
}
}
else if(A[end] > A[mid]) {
if(K < A[mid]) {
end = mid-1;
}
else if(K > A[mid]) {
start = mid+1;
}
}
else {
System.out.println(-1);
break;
}
}
}
System.exit(0);
}
}
public static int getKeyIndex(int[] A, int p, int r, int key)
{
// invalid input indices, return -1
if (p > r)
return -1;
// if array if only one entry, if equals to key return index else return -1;
if (p == r)
{
if (A[p] == key)
return p;
else
return -1;
}
// if array has only two entries, if either of indices value equals key return index, else -1
if (p+1 == r)
{
if (A[p] == key || A[r] == key)
{
if (A[p] == key)
return p;
else
return r;
}
else
return -1;
}
// get middle index
int mid = (p + r)/2;
// if value at mid index, return mid
if (A[mid] == key)
return mid;
//checking for increasing sequence, that is A[mid-1] < A[mid] < A[mid+1] and key less than A[mid]
// search for key left part
else if (A[mid-1] < A[mid] && A[mid] < A[mid+1] && key < A[mid])
return getKeyIndex(A, p, mid-1, key);
// else search in right part of the array.
else
return getKeyIndex(A, mid+1, r, key);
}
Please point out, if you find any error.
Time complexity : O(logn)
Use a modified binary search.
1. Check if the pivot element is equal to the given element. If yes, return the index.
2. If the pivot element != given element, compare the pivot element with it's adjacent elements that are to the left and to the right
Here 3 cases arise:
3a. The pivot element is the boundary element between the monotonically increasing and monotonically decreasing subarrays.
. i. Apply this modified binary search in the left subarray
ii. If the given element is not found in the left subarray apply this modified binary search AGAIN in the right subarray
3b. The pivot element lies completely in the monotonically increasing subarray.
i. if the given element < pivot element, look up in the left subarray
ii. if the given element > pivot element look up in the right subarray.
3c. The pivot element lies completely in the monotonically decreasing subarray.
i. if the given element < pivot element, look up in the right subarray
ii. if the given element > pivot element look up in the left subarray
if the given element is not found, return -1.
Even after applying binary search twice for case 3a, the complexity is still O(lgn), because it is at most once that the binary search is applied twice and each application of binary search has time complexity O(lgn)
Will not work!
Example:
array =1, 3, 5, 7, 9, 6, 4
key = 6
first iteration:
pivot = 7, in increasing part.
key<pivot, so you will search left subarray and not find 6
@__xy__
It will work!
Read point #3a
>> ii. If the given element is not found in the left subarray apply this modified binary search AGAIN in the right subarray
It doesn't work!
For the example that I gave, 3b applies. (not 3a)
The pivot element (=7) is not at the boundary of increasing and decreasing parts. It lies completely in the increasing part.
It doesn't seem possible to search the element in o(logn) without calculating the pivot
- Amit July 18, 2013suppose case 1: arr[]={1,2,3,22,23,25,30,27,21,11,10}
case 2: arr[]={1,2,3,21,23,25,30,27,22,11,10}
and suppose key is 22
in both the arrays middle element is 25,and arr[low]=1,arr[high]=10,arr[mid-1]=23,arr[mid+1]=30.
so,it seems impossible to decide whether to look in left subarray or right..In 1st example 22 lies in left subarray while in 2nd it lies in right subarray. Correct me if I am wrong