# Solution: Sorted Array Multiple Search

Solution for the Sorted Array Multiple Search Problem.

We'll cover the following

## 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$
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.