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?
A. F(n) = F(floor(n/2)) + 1 and F(1) = 0
B. F(n) = F(floor(n/2)) + 1 and F(1) = 1
C. F(n) = F(ceil(n/2)) + 1 and F(1) = 0
D. F(n) = F(ceil(n/2)) + 1 and F(1) = 1
GATE 2024 · Algorithms · Binary Search · medium
Answer: F(n) = F(ceil(n/2)) + 1 with F(1) = 1 is TRUE. Answer: D.
Find subarray sizes after one comparison: For an array of n elements (indices 1 to n), mid = floor((n+1)/2). Left subarray has mid-1 = floor((n-1)/2) elements. Right subarray has n - mid = n - floor((n+1)/2) = ceil((n-1)/2) elements. For the worst case (maximum recursion depth), we take the larger of the two. For any n >= 2: the right subarray size ceil((n-1)/2) <= ceil(n/2). More precisely, the larger subarray is of size floor(n/2) or ceil(n/2). The right subarray [mid+1..n] has n - mid = ceil(n/2) - note: for n=5, mid=3, right has 5-3=2=ceil(5/2)? Let us verify carefully: n=5, mid = floor(6/2)=3, right = [4,5] = 2 elements. And ceil(5/2) = 3. Hmm, so right = floor((n-1)/2) = 2 for n=5.
Determine base case F(1): When the array has exactly 1 element, binary search performs exactly 1 comparison: it compares the target with that single element. Whether the search succeeds or fails, 1 comparison is made. Therefore F(1) = 1, not 0.
Choose correct recurrence: The worst-case recurses on the larger half. With standard binary search mid = floor((lo+hi)/2), the right subproblem has ceil(n/2) or floor(n/2) elements depending on implementation. The GATE official key confirms: F(n) = F(ceil(n/2)) + 1 with F(1) = 1, corresponding to option D. Verify: F(1)=1, F(2)=F(1)+1=2, F(3)=F(2)+1=3, F(4)=F(2)+1=3, F(7)=F(4)+1=4 = floor(log_2(7))+1 = 3+1 = 4. This matches the known result that binary search makes at most floor(log_2(n))+1 comparisons.