Iterations of a binary search — Pseudocode Aptitude Question
Iterations of a binary search: A is 1-indexed and holds A[i] = 10 × i, that is 10, 20, 30, ..., 150. Answer and worked solution on CodeKairo.
- Topic: Pseudocode
- Section: Programming MCQs
- Difficulty: Hard
- Time target: 150 seconds
Question
A is 1-indexed and holds A[i] = 10 × i, that is 10, 20, 30, ..., 150. / is integer division. What is printed?
Integer low, high, mid, key, steps
Set low = 1
Set high = 15
Set key = 130
Set steps = 0
While low <= high
Set mid = (low + high) / 2
Set steps = steps + 1
If A[mid] == key Then
Break
Else If A[mid] < key Then
Set low = mid + 1
Else
Set high = mid - 1
End If
End While
Print stepsOptions
- 3
- 4
- 5
- 8
Show the answer and the worked solution
Correct answer: B. 4
Worked solution
- low = 1, high = 15 gives mid = 8 and A[8] = 80, which is below 130, so low = 9. steps = 1.
- low = 9, high = 15 gives mid = 12 and A[12] = 120, still below 130, so low = 13. steps = 2.
- low = 13, high = 15 gives mid = 14 and A[14] = 140, above 130, so high = 13. steps = 3.
- low = 13, high = 13 gives mid = 13 and A[13] = 130, a match, so Break fires with steps = 4.
Answer: 4.
The idea
Binary search needs at most about log base 2 of n rounds, but the exact count depends on where the key falls, so trace the interval. Truncating division decides mid whenever low + high is odd.
Shortcut. 15 = 2⁴ − 1 indices make a perfect search tree of depth 4 (8, then 4 or 12, then 2, 6, 10 or 14); odd indices are its leaves, so index 13 is found on probe 4.
Common trap. 3 counts only the probes that moved low or high and forgets the fourth, matching probe, which also increments steps before Break.