Binary Search Quiz

8 questions10 minPass: 60%+10 XP on first pass

The classic template, lower bound, overflow-safe mid, rotated arrays and binary search on the answer.

Free account · see your score, answers and explanations, earn XP

Question 1
About how many comparisons does binary search need on 1,000,000 sorted numbers?
About 1,000About 1,000,000About 20About 500,000
Question 2
Why is mid = lo + (hi - lo) / 2 preferred over (lo + hi) / 2 in Java?
It is fasterlo + hi can overflow a 32-bit intIt rounds up instead of downIt works on unsorted arrays

Question 3

What does this return for nums = [1, 3, 5, 7], target = 4?

lo, hi = 0, len(nums)
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid
print(lo)

Question 4Select all that apply
Which statements about binary search are true? (select all that apply)
It needs sorted (or monotonic) dataIts time complexity is O(log n)It works on any unsorted arrayIt always needs O(n) extra space
Question 5
In a rotated sorted array like [4, 5, 6, 7, 0, 1, 2], what is always true at any mid?
Both halves are sortedAt least one half is sortedNeither half is sortedThe minimum is at mid
Question 6
"Binary search on the answer" works when…
If a value x is feasible, every larger value is also feasible (or every smaller one)The input array is sortedThe answer is always an indexThere are no duplicates
Question 7
Koko eats piles [3, 6, 7, 11] and has h = 8 hours. What is the minimum speed k?
Question 8
Which loop pairing can cause an infinite loop?
while lo <= hi with lo = mid + 1 / hi = mid − 1while lo < hi with lo = mid + 1 / hi = midwhile lo < hi with lo = mid / hi = mid − 1 (and mid rounded down)None of these