Solution: Multiple Search with Duplicates

Solution

Given a key $q$, our goal is to find the first (top) occurrence of this key in the array $K$. For example, if $K = \{3,6,6,7,7,7,7,9\}$ and the key $q$ is $7$, then the first occurrence of this key is located at index $3$. Of course, we can find one of the occurrences of the key by simply launching the binary search. Afterward, we can find the first occurrence of the key by consecutively checking the element before the position of the found element, as illustrated in the pseudocode below.

---

 $NaiveBinarySearchWithDuplicates(K [0\dots n − 1], q)$:
 $minIndex ← 0$
 $maxIndex←n−1$ ...