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$
 while $maxIndex ≥ minIndex$:
 $midIndex \leftarrow ⌊(minIndex + maxIndex)/ 2⌋$
 if $K[midIndex] = q$:
  $top ← midIndex$
  while $top > 0$ and $K[top − 1] = K[top]$:
    $top←top−1$
  return $top$
 else if $K[midIndex] < q$:
  $minIndex ← midIndex + 1$
 else:
  $maxIndex ← midIndex − 1$
return $−1$

---

Stop and think: What is the running time of this algorithm?

This algorithm might become slow in the case of an array with many duplicates. For example, if a single duplicated element accounts for half of an array, $NaiveBinarySearchWithDuplicates$ takes linear $O(n)$ time instead of logarithmic $O(log n)$ time. This problem is fixed in the pseudocode below.

---

 $BinarySearchWithDuplicates(K [0..n − 1], q)$:
 $minIndex ← 0$
 $maxIndex←n−1$
 $result ← −1$
 while $maxIndex ≥ minIndex$:
 $midIndex ← ⌊(minIndex + maxIndex)/ 2⌋$
 if $K[midIndex] = q$:
  $maxIndex ← midIndex − 1$
  $result ← midIndex$
 else if $K[midIndex] < q$:
  $minIndex ← midIndex + 1$
 else:
  $maxIndex ← midIndex − 1$
return $result$

---

Code

Here is the implementation of the algorithm above.