March 12, 2013
I found today’s exercise on a discussion forum for learning programmers. It looks to me like homework, but the posting was old enough that I don’t think we have to worry about doing someone’s homework for them — unless the teacher reuses the same problems from one year to the next.
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).
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.