[Java] Binary search find first and last occurrence

We saw how to implement binary search both recursively and iteratively, however if the input has duplicates, the result we get is just one possible occurrence of the item.

If we want to find the very first or very last occurrence of the item, we need to tweak the search a bit.

Specifically, we use a temporary variable initialized to -1 and if we find the item in the mid position, we do NOT return yet; instead, we store the matching position in this variable and continue the search as if we hadn't found the element yet.

We do NOT simply walk left or right from there, otherwise we go back to O(N) time.

If we are looking for the first occurrence, we continue the search on the left of the middle, since any prior duplicate must be there. Otherwise we continue on the right, since the last occurrence must be after the current item.

The important part is that at each new step, IF we find the element, we update our temporary result since we're getting closer to the first or last occurrence we want.

At the end, we either did not find the element, so return our default -1 from the temporary result, or we have the exact first or last location of the element there.

This logic is easily implemented iteratively, otherwise in the recursive case we would need to pass an additional variable as input to track the last found occurrence. Up to you whatever road you prefer.

You can check my implementations of binarySearchFirstOccurrence and binarySearchLastOccurrence on my Gist alongside tests in BinarySearchFirstOccurrenceJTests and BinarySearchLastOccurrenceJTests

For the recursive version check out instead binarySearchFirstOccurrenceRecursive and binarySearchLastOccurrenceRecursive on my Gist alongside tests in BinarySearchFirstOccurrenceRecursiveJTests and BinarySearchLastOccurrenceRecursiveJTests

 

Note that the code has been tweaked to make it generic, and can be further improved by accepting a Comparator in input, which would allow the search to work correctly also for elements that are not following natural ordering.