GATE 2026 DA – Question 31
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*)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 10
Explanation
Each recursive step makes one three-way comparison with the middle element and then keeps at most half of the remaining elements (at most $\lfloor n/2 \rfloor$). Starting from 1000 elements the sizes shrink as at most 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1, and then the range is empty. That takes 10 comparisons before the search ends without finding y. This is $\lfloor \log_2 1000 \rfloor + 1 = 10$.