Question Details

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)

Show Answer
Correct Answer
10

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:

⌊ log 2 ( N ) ⌋ + 1

Substituting N = 1000 into the formula:

log 2 ( 1000 ) ≈ 9.966

Taking the floor of this value and adding 1, we get:

⌊ 9.966 ⌋ + 1 = 9 + 1 = 10

Therefore, the maximum number of comparisons that may have to be performed is 10.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • computer science and information technology

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.

  • GATE
  • intermediate
  • 3 hours
  • computer science and information technology

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: