Question is from here
You are given an array of length n that is filled with two symbols; all m copies of one symbol appear first, at the beginning of the array, followed by all n−m copies of the other symbol. You are to find the index of the first copy of the second symbol, m, in time O(log m).
Solution:
The obvious solution is binary search. Pick the midpoint of the array; if the item there is the first symbol, search recursively in the right half of the array, otherwise search recursively in the left half of the array, stopping when the sub-array has been reduced to a single item. But that takes time O(log n), which violates the conditions of the exercise.
First symbol is number 1 and second symbol is number 2.
public class An_Array_Of_Two_Symbols {
public static void main(String[] args) {
int[] a = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2};
findIndex(a, 0, a.length);
System.out.println();
int[] b = {1,1,1,1,1,1,2,2,2,2};
findIndex(b, 0, b.length);
}
private static void findIndex(int[] a, int s, int e) {
if(s == e){
System.out.println("index: " + (s + 1));
return;
}
int mid =(int) Math.ceil((s + e)/2);
if(mid == 0) {
System.out.println("index: " + (mid + 1));
return;
}
if(a[mid] == 1 && a[mid + 1] == 2) {
System.out.println("index: " + (mid + 1));
return;
}else if(a[mid] == 1) {
findIndex(a, mid, e);
} else if(a[mid] == 2 && a[mid - 1] == 1) {
System.out.println("index: " + mid);
return;
} else {
findIndex(a, s, mid - 1);
}
}
}
Output:
index: 15 index: 6
Isn’t this O(log n)? It looks like the binary search described in the problem that won’t satisfy the O(log m) requirement.
Other than that, it certainly will find the correct index.
In my solution I have stated that it is in O(log n), but do you have any suggestion that how it can be done in O(log m). Thanks.
Your findIndex runs in O(log n) time given boundaries of 0 and array.length, so create a second method that will find better boundaries in O(log m) time.
Something like this:
findIndexOLogM(int[] a, int s, int e){
if (a[s]==1 && a[e]==1) return findIndexOLogM(a,e, min(2*e, a.length));
if (a[s]==1 && a[e]==2) return findIndex(a,s,e);
if (a[s]==2) throw new Exception();
}
then you can call it like this:
findIndexOLogM(a,0,1);
Now you’ve got a recursive loop that will find the boundaries in O(log m) time, but you’ve still got to run your findIndex method which runs in O(log n) time.
The catch here, is now your findIndex method isn’t starting with a search space of n, but instead with a smaller search space of worst case: m! (m exclamation point, not m factorial)
You end up with a search time of worst case 2*log(m), but since you can factor out constants when calculating Big O time, it’s O(log m).