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)
ANSWER
At most 10 comparisons are needed when is not in the array.
Official answer: 10Source: Official answer key, GATE 2026 DA (IIT Guwahati)
Each recursive step makes one three-way comparison of with the middle element. It then recurses on the left or right part. For a subarray of elements, these parts have and elements. Since , the larger part has elements.
If is absent, the search can never stop early on equality. It keeps going until the subarray is empty, so the worst case follows the larger part every time.
Worst-case subarray sizes: .
One comparison is made at every non-empty subarray, with sizes . That is 10 comparisons. The search then reaches the empty subarray and ends without any further comparison.
Check with the closed form: the worst case is , because .
KEY IDEA
Binary search on elements halves the range at each comparison. An unsuccessful search runs until the range is empty, so the worst case is comparisons when each step uses one three-way comparison.
WATCH OUT FOR
Answering by coincidence, or counting the final empty-range check as an extra comparison and answering 11. Another slip is using and writing 9 or 10 without checking the halving sizes.
From the GATE 2026 DA paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes
