CLRS Solutions | Exercise 2.3-5

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta(\lg n)$.

Here is the pseudocode if you prefer iterative solutions …

$$\textsc {Iterative-Binary-Search }(A, v)$$$$\begin{aligned}1& \quad low=A[1] \\2& \quad high=A[A.length] \\3& \quad \textbf {while }low\leq\,\,high \\4& \quad \qquad mid=\lfloor \textsc {}(low+high)/2\rfloor \\5& \quad \qquad \textbf {if }v==A[mid] \\6& \quad \qquad \qquad \textbf {return }mid \\7& \quad \qquad \textbf {elseif }v>A[mid] \\8& \quad \qquad \qquad low=mid+1 \\9& \quad \qquad \textbf {else } \\10& \quad \qquad \qquad high=mid-1 \\11& \quad \textbf {return }\text { NIL } \\\end{aligned}$$

And here is the recursive one …

$$\textsc {Recursive-Binary-Search }(A, v, low, high)$$$$\begin{aligned}1& \quad \textbf {if }low>high \\2& \quad \qquad \textbf {return }\text { NIL } \\3& \quad mid=\lfloor \textsc {}(low+high)/2\rfloor \\4& \quad \textbf {if }v==A[mid] \\5& \quad \qquad \textbf {return }mid \\6& \quad \textbf {elseif }v>A[mid] \\7& \quad \qquad \textsc {Recursive-Binary-Search}(A,\,v,\,mid+1,\,high) \\8& \quad \textbf {else } \\9& \quad \qquad \textsc {Recursive-Binary-Search}(A,\,v,\,low,\,mid-1) \\\end{aligned}$$

Intuitively, in worst case, i.e. when $v$ is not at all present in $A$, we need to search over the whole array to return $\text {NIL}$. In other words, we need to repeatedly divide the array by 2 and check either half for $v$. So the running time is nothing but how many times the input size can be divided by 2, i.e. $\lg n$.

For recursive case, we can write the recurrence as follows …

\[T(n) = \begin {cases} \Theta(1) & \text { if } n = 1, \\ T((n - 1)/2) + \Theta(1) & \text { if } n > 1 \end {cases}\]