Binary search to find the last and first occurance of an key

Given an sorted array with duplicates how do we find the first and last occurance of a Key?

There are three solutions in the code fragment below, all take log(n); the most efficient is from Bentley ( see Programming Pearls Column 9, a bit trickier to understand )

The obvious way to solve it is to keep saving the last found location. In case of normal binary search, we stop one the key is found. But to find the first occurrence (or the last occurance), instead of stopping, we set the upper bound to mid-1 ( and to find the last occurrence, we set the lower bound to mid+1 ) and continue. When the element is not found, we simply return the last occurrence. Bentley's method from Programming Pearls is obviously more efficient, since it eliminates one comparison in the inner loop (however, I found it a bit trickier to understand and implement).


No comments: