Hi, I don't quite understand the solution to Chapter 10, Problem 62C of Data Structures and Algorithms in Java (6th Edition).

The question is to design a variation of binary search for performing the get(k) operation on a sorted search table that includes duplicates.

But what happens in step 1? is it a search for the first key value of k? In step 2, I don't understand what is being backtraced? The table? And why? In step 3, why are we now looking for something not equal to k?

Could someone maybe provide an example?

Thanks in advance!

EDIT: The exact question is:

The operation get(k) for the multimap ADT is responsible for returning a collection of all values currently associated with key k. Design a variation of binary search for performing this operation on a sorted search table that includes duplicates, and show that it rins in time O(s+log n), where n is the number of elements in the dictionary and s is the number of entries with given key k.