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 (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 }\,\textsc{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 }\,\textsc{NIL} \\ 3& \quad mid\,=\,\lfloor (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}\]
If you have any question or suggestion or you have found any error in this solution, please leave a comment below.
E 2.3-4
Solution Index
E 2.3-6

Archived Comments

These comments were imported from the previous Disqus comment system.

Stv Cl Mar 10, 2023
Hi, sorry for my bad English. There is an error in Iterative-Binary-Search. low and high must be index, and not value.
Ovidiu Oprea Jun 4, 2023
Tried the recursive variant in Python and it doesn't return your value unless you set return Recursive-Binary-Search(A, v, mid + 1, high) and return Recursive-Binary-Search(A, v, low, mid - 1) in the elseif and else branches. Otherwise you get None or the return of your first run through the recursive function. The return mid is overridden.
Andrea Attardo Oct 24, 2022
I got it now. Thanks for clarifying.
Atekihcan Oct 24, 2022
We are comparing the middle element, and then checking half of rest of the elements in the array, which is \((n - 1)/2\), as you are taking out the middle element from the consideration, hence \((n - 1)\). But practically either way, worst case runtime is going to be \(\lg(n)\). \(n\) or \((n - 1)\) is not going to make any difference there. Try taking a practical example, say an array with 1024 elements. If you consider \(n/2\), you'll reach down to 1 element in 10 steps. If you consider \((n - 1)/2\), same 10 steps will be required to reach down to 1 element, just that in every step, you'll have two arrays, but not of same size.