Algorithms · Question 4 · Easy
What is the maximum number of probes (middle-element checks) binary search needs to search a sorted array of 1000 elements?
- 9
- 11
- 500
- 10
Answer and explanation
Answer: D. 10
Explanation: Each probe at least halves the range: in the worst case 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 elements remain to be probed, which is at most 10 probes, i.e. floor(log2 1000) + 1 = 10.
Previous: Bubble sort is implemented with a flag that stops the algorithm when a pass… · Next: Merge sort is an example of which algorithm design technique?
Practise algorithms
Try a fresh set of algorithms questions with an explanation after every answer, free and without signing up: Algorithms practice. Or sit a full placement mock test.
More algorithms questions
- What is the worst-case time complexity of binary search on a sorted array of n…
- Which of the following sorting algorithms is NOT comparison-based?
- Bubble sort is implemented with a flag that stops the algorithm when a pass…
- Merge sort is an example of which algorithm design technique?
- What is the solution of the recurrence T(n) = 2T(n/2) + n, with T(1) = 1?
- What is the maximum number of swaps selection sort performs on an array of n…
- Quick sort always picks the last element as the pivot. For which input does it…
- What does the following function return for f(4096)?
- Coins of value ₹1, ₹3 and ₹4 are available in unlimited supply. A greedy…
- Insertion sort is applied to [5, 2, 4, 6, 1, 3]. What does the array look like…
More technical & programming practice
Object-Oriented Programming · DBMS · SQL · Operating Systems · Computer Networks · Software Engineering · Cloud & DevOps · GenAI Basics
LogicWiz Exams home · All practice topics · Placement mock tests · Daily 10 challenge