Solution: Sorted Array Multiple Search

Solution

To solve the Multiple Search Problem, let’s first look at the Binary Search Problem to search a single key in a sorted array of keys.

$\rule[0 pt]{1000 pt}{0. pt}$

Sorted Array Search Problem

Search a key in a sorted array of keys.

Input: A sorted array $K$ $= [k_{0},\ldots,k_{n-1}]$ of distinct integers (i.e.,$k_{0} < k_{1} <\ldots< k_{n-1}$) and an integer $q$.

Output: Check whether $q$ occurs in $K$.

$\rule[0 pt]{1000 pt}{0. pt}$

A naive way to solve this problem is to scan the array $K$ (running time $O(n)$). The $BinarySearch$ algorithm below solves the problem in $O(log (n))$ time. It is initialized by setting $minIndex$ equal to $0$ and $maxIndex$ equal to $n−1$. It sets $midIndex$ to $(minIndex + maxIndex)/2$ and then checks to see whether $q$ is greater than or less than $K$[$midIndex$]. If $q$ is larger than this value, then $BinarySearch$ iterates on the subarray of $K$ from $minIndex$ to $midIndex − 1$; otherwise, it iterates on the subarray of $K$ from $midIndex + 1$ to $maxIndex$. The iteration eventually identifies whether $q$ occurs in $K$.

---

 $BinarySearch(K[0..n − 1], q)$
 $minIndex$ $\leftarrow$ 0
 $maxIndex$ $\leftarrow$ $n−1$
 while $maxIndex ≥ minIndex$:
  $midIndex$ $\leftarrow$ ⌊($minIndex + maxIndex$)/ 2⌋
  if $K$[$midIndex$] $=$ $q$:
   return $midIndex$
  else if $K$[$midIndex$] $<$ q:
   $minIndex$ $\leftarrow$ $midIndex + 1$
  else:
   $maxIndex$ $\leftarrow$ $midIndex − 1$
 return “key not found”

---

For example, if $q = 9$ and $K = [1, 3, 7, 8, 9, 12, 15]$, $BinarySearch$ would first set $minIndex = 0$, $maxIndex = 6$, and $midIndex = 3$. Since $q$ is greater than $K$[$midIndex$] $= 8$, we examine the subarray whose elements are greater than $K$[$midIndex$] by setting $minIndex = 4$, so that $midIndex$ is recomputed as $(4 + 6)/ 2 = 5$. This time, $q$ is smaller than $K$ [$midIndex$] $= 12$, and so we examine the subarray whose elements are smaller than this value. This subarray consists of a single element, which is $q$.

The running time of $BinarySearch$ is $O(log(n))$ since it reduces the length of the subarray by at least a factor of $2$ at each iteration of the while loop. Note however that our grading system is unable to check whether you implemented a fast $O(log(n))$ algorithm for the sorted array search or a naive $O(n)$ algorithm. The reason is that any program needs a linear time in order to just read the input data. For this reason, we asked you to solve the multiple search problem.

Code

Here is an implementation of the challenge. Hit the “Run” button and observe the output.