Question

Let \(A\) be a sorted array containing 1000 distinct integers. You perform a recursive binary search on \(A\) to find an element \(y\). Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than \(y\).

The maximum number of comparisons that may have to be performed if \(y\) is not an element of \(A\) is __________. (Answer in integer)

Hint:

Each comparison roughly halves the search space, so count how many times 1000 can be halved before nothing is left.

Answer 1

Correct Answer: 10

Step 1: Recall how a three-way comparison binary search works.
At each recursive step, the search looks at the middle element of the current sub-array and checks whether it is equal to, less than, or greater than the target \(y\). If equal, the search stops (found). If less, the search continues on the right half. If greater, it continues on the left half. Since \(y\) is not present in \(A\), the "equal" case never triggers, and the search keeps halving the search space until nothing is left to search.

Step 2: Model the search size after each comparison.
Starting with \(n = 1000\) elements, each comparison narrows the search down to roughly half the elements (rounding down), because one element is examined (and ruled out as unequal) and the rest is split into two halves of which only one is kept. This continues until the sub-array size becomes 0, meaning \(y\) is confirmed absent.

Step 3: Count how many times 1000 can be halved.
The number of comparisons needed in the worst case to search \(n\) elements this way is:
\[ \text{comparisons} = \lfloor \log_2 n \rfloor + 1 \]
Substituting \(n = 1000\):
\[ \log_2 1000 \approx 9.966 \]
\[ \lfloor 9.966 \rfloor + 1 = 9 + 1 = 10 \]

Step 4: Sanity check with a direct doubling argument.
\(2^9 = 512\) and \(2^{10} = 1024\). Since \(512 < 1000 \leq 1024\), it takes 10 halving steps (comparisons) in the worst case to shrink a search space of 1000 elements down to nothing, confirming the formula.

Final Answer:
The maximum number of comparisons needed is 10. \[ \boxed{10} \]