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

A neat way to see this without memorising a formula is to picture binary search as a decision tree. Every internal node of this tree represents one comparison against a middle element, has a "target is smaller" branch and a "target is larger" branch, and every leaf represents "search space is now empty, target is absent".

A tree where each internal node has 2 branches and needs to represent every possible "gap" outcome for a missing element needs enough leaves to cover all $n+1$ gaps (before the first element, between each pair of elements, and after the last element). With $n = 1000$ elements, there are $1001$ such gaps.

A binary tree with depth $d$ can have at most $2^d$ leaves. We need

\[ 2^d \ge 1001 \]

Check successive powers of 2: $2^9 = 512$, which is too small, and $2^{10} = 1024$, which is enough to cover all 1001 gaps. So the smallest depth that works is $d = 10$.

Each level of this decision tree corresponds to exactly one comparison in the actual search, so the worst-case unsuccessful search needs 10 comparisons before it can conclude the element is not present.

This also lines up with just repeatedly halving 1000: $1000 \to 500 \to 250 \to 125 \to 62 \to 31 \to 15 \to 7 \to 3 \to 1 \to 0$, which is 10 halving steps to reach an empty range.

\[ \boxed{10} \]