algorithm - Finding multiple entries with binary search

Question

I use standard binary search to quickly return a single object in a sorted list (with respect to a sortable property).

Now I need to modify the search so that ALL matching list entries are returned. How should I best do this?

Answer 1

Well, as the list is sorted, all the entries you are interested in are contiguous. This means you need to find the first item equal to the found item, looking backwards from the index which was produced by the binary search. And the same about last item.

You can simply go backwards from the found index, but this way the solution may be as slow as O(n) if there are a lot of items equal to the found one. So you should better use exponential search: double your jumps as you find more equal items. This way your whole search is still O(log n).