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