Let \(F(n)\) denote the maximum number of comparisons made while searching for an entry in a sorted array of size \(n\) using binary search.
Which ONE of the following options is TRUE?
Answer
(A)
Explanation
Binary search compares the target with the middle element. Either it matches, or the search continues in just one of the two parts left after removing the middle. With \(n\) elements the larger part has \(\lfloor n/2 \rfloor\) elements, so in the worst case one comparison is followed by a search of size \(\lfloor n/2 \rfloor\):
\[F(n) = F(\lfloor n/2 \rfloor) + 1, \quad F(1) = 1,\]
which solves to \(F(n) = \lfloor \log_{2} n \rfloor + 1\).
Option B searches both halves, C forgets the comparison just made (so \(F\) would never grow), and D discards only one element per step, which describes linear search.
Answer: A