A be a sorted array containing 1000 distinct integers. You perform 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 max number of comparisons that may have to be performed if y is not an element of A is . (Answer in int)
Solution :
The correct answer is 10.
To find the maximum number of comparisons performed during a binary search on a sorted array of size N when the element y is not present, we can analyze how the search space decreases at each step.
In a binary search, each step compares the target value y with the middle element of the current subarray. If y is not equal to the middle element, the search continues in either the left or the right subarray. Each comparison reduces the search space to at most half of its previous size.
Let N be the number of elements in the array. In this case, N = 1000. Let's trace the maximum remaining size of the search space after each comparison step:
After comparison 1: at most 500 elements remain.
After comparison 2: at most 250 elements remain.
After comparison 3: at most 125 elements remain.
After comparison 4: at most 62 elements remain.
After comparison 5: at most 31 elements remain.
After comparison 6: at most 15 elements remain.
After comparison 7: at most 7 elements remain.
After comparison 8: at most 3 elements remain.
After comparison 9: at most 1 element remains.
After comparison 10: 0 elements remain.
Thus, it takes at most 10 comparisons to reduce the search space to 0 and conclude that y is not an element of the array.
More formally, the maximum number of comparisons for a binary search on an array of size N is given by the formula:
Substituting N = 1000 into the formula:
Taking the floor of this value and adding 1, we get:
Therefore, the maximum number of comparisons that may have to be performed is 10.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare effectively for GATE 2026 Computer Science & Information Technology (CS & IT) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Data Structures, Algorithms, Operating Systems, DBMS, Computer Networks, Theory of Computation, Compiler Design, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 preparation strategy.
Prepare for GATE 2026 Electrical Engineering (EE) with high-quality study material, previous year question papers, mock tests, syllabus updates, exam pattern, and expert preparation strategies. Master core EE subjects including Power Systems, Control Systems, Electrical Machines, Circuit Theory, Signals & Systems, Power Electronics, and Measurements to secure a top rank in GATE 2026.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.