Amazon Interview Question Software Engineer / Developers
Find the lower bound, upper bound (indices) of the element to be searched , both can be done in
O(log n) with slight modification to the usual binary search algorithm, now the difference between the upper and lower bounds, give u the number of occurences of the req element. O(logn) in all.
Usual Binary Search Algo:
binary_search(A, target):
lo = 1, hi = size(A)
while lo <= hi:
mid = lo + (hi-lo)/2
if A[mid] == target:
return mid
else if A[mid] < target:
lo = mid+1
else:
hi = mid-1
The above returns an index(we are not sure if
this is the lower or upper index for repeated eles) of the element found.i
The below algo returns the lower bound of the repeated element
binary_search(lo, hi, p):
while lo < hi:
mid = lo + (hi-lo)/2
if p(mid) == true:
hi = mid
else:
lo = mid+1
if p(lo) == false:
complain
return lo
Like wise u can write an algo to find the upper bound
RAM, correct me if i am wrong.
We do binary search for (element-1) to get the first index of element
and element+1 to get the last index of element.
Even if all the elements are same, we can still do it in o(logn)
@ V,
Use the 2nd algo which I posted above to find the lower bound.
Your approach fails because we don't know whether (element-1)
or (element+1) exists in the given array.
@V even if the elements don't exit, binary search gives us the index where the element should be inserted. However, the above approach fails in element-1 & element+2 exist multiple times.
Something like searching for 2 in the following array.
{1,1,1,1,1,1,1,1,1,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3}
Not sure I understand how to find the first occurrence of the element. You do binary search and say you find the element, then search again within the lower range? How do you know when to stop? Thanks.
public class BinarySearch {
/**
* @param args
*/
public static void main(String[] args) {
// int b [] = {7, 7,7,7,7,7,7,7,7,7,7,7,10};
int b [] = { 2,2,2,2};
int index = binarySearch(2,b);
System.out.println(index);
}
private static int binarySearch(int no, int[] a) {
System.out.println(findHigherIndex(no, 0, a.length-1, a));
System.out.println(findLowerIndex(no, 0, a.length-1, a));
return findHigherIndex(no, 0, a.length-1, a)-findLowerIndex(no, 0, a.length-1, a)+1;
// return performBinarySearch(no, 0, a.length, a);
}
private static int findHigherIndex(int no, int low, int high, int[] a) {
int mid = -1;
while (low < high) {
mid =(low+high)/2;
if(no!=a[high] && no==a[high-1]){
high = high-1;
break;
} else if (high==a.length-1 && a[high]==no) {
break;
} else if(no >= a[mid]) {
low = mid;
} else if(no < a[mid]){
high = mid;
}
}
return high;
}
private static int findLowerIndex(int no, int low, int high, int[] a) {
int mid = -1;
while (low < high) {
mid =(low+high)/2;
if(no==a[low] && low==0 ) {
break;
} else if (no!=a[low] && no==a[low+1]){
low = low+1;
break;
} else if(no > a[mid]) {
low = mid;
} else if(no <= a[mid]){
high = mid;
}
}
return low;
}
}
private static int findHigherIndex(int no, int low, int high, int[] a) {
int rindex= -1;
while (low < high) {
mid =(low+high)/2;
if(no!=a[high] && no==a[high-1]){
rindex= high-1;
break;
} else if (high==a.length-1 && a[high]==no) {
break;
} else if(no >= a[mid]) {
low = mid;
} else if(no < a[mid]){
high = mid;
}
}
return rindex;
}
private static int findLowerIndex(int no, int low, int high, int[] a) {
int lindex= -1;
while (low < high) {
mid =(low+high)/2;
if(no==a[low] && low==0 ) {
break;
} else if (no!=a[low] && no==a[low+1]){
lindex= low+1;
break;
} else if(no > a[mid]) {
low = mid;
} else if(no <= a[mid]){
high = mid;
}
}
return lindex;
}
I made slight change, to accommodate if the element is not found in the sorted list.
In the main, check if lindex||rindex==-1 number of occurances=0.
Please correct me if i am wrong!
Binary search till you hit the element and then go back and forth till the element changes. Return the count. Average running time=O(log n),worst case = O(n) where all elements are the required element
- Metta September 25, 2010