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.