Challenge: Multiple Search with Duplicates

Donald Knuth, author of The Art of Computer Programming, famously said: “Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky.” He was referring to a modified classical Binary Search Problem.

Problem

---

Binary Search with Duplicates Problem

Find the index of the first occurrence of a key in a sorted array.

Input: A sorted array of integers (possibly with duplicates) and a sequence of $m$ positive integers $q_0,q_1,\ldots,q_{m−1}$.

Output: Index of the first occurrence of $q$ in the array or “$−1$” if $q$ does not appear in the array.

---

When Knuth asked professional programmers at top companies like IBM to implement an efficient algorithm for binary search with duplicates, 90 percent of them had bugs—year after year. Indeed, although the binary search algorithm was first published in 1946, the first bug-free algorithm for binary search with duplicates was published only in 1962! Similar to the previous problem, we ask you to search for $m$ ...