An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. At each step, compare the target to the middle element: if equal, the search is done; if smaller, search the left half; if larger, search the right half.
Binary search is how you find page 412 in a thick book: open near the middle, see whether the page number there is too high or too low, and keep only the half that must contain 412. It works because page numbers are in order; if the pages were shuffled, the number you opened to would tell you nothing.
Showing a random 20 of 50 problems.
Example 1
medium
Why is sorting first and then binary-searching often slower than a single linear search for a one-off lookup?
Example 2
medium
An off-by-one bug uses high=mid instead of high=mid−1. When does it fail catastrophically?
Example 3
medium
Linear search vs binary search on n=65,536. Worst-case comparison counts?
Example 4
medium
Search for 7 in sorted [1,3,5,7,9,11,13] (indices 0-6). Trace the midpoints. How many comparisons?Binary search for 7: mid
Example 5
hard
A student tries binary search on [3,1,5,2,7] for target 5. What is the result, and why?
Example 6
easy
Sorted list of 256 items, worst-case comparisons?256 → 128 → … → 1: ⌈log₂ 256⌉ + 1
Example 7
hard
Trace binary search for target =42 in a sorted [5,12,19,26,33,40,47,54,61,68,75,82] (indices 0-11). Midpoints, count, result?
Example 8
challenge
Two sorted lists of sizes 1000 and 8 are each binary-searched once. Compare their worst-case comparison counts and explain why the gap is small.
Example 9
medium
Search for 11 in sorted [1,3,5,7,9,11,13] (indices 0-6). Trace midpoints and count comparisons.Step 2 — lo=4, mid=5 (value 11): match found; total 2 comparisons
Example 10
easy
Binary search requires the list to be in what state?
Example 11
hard
Binary search finds the smallest integer x such that x3≥100 over 1≤x≤100. What is x?
Example 12
easy
Binary search is a classic example of which algorithmic paradigm?
Example 13
medium
Search for 2 in [1,3,5,7,9,11,13] (indices 0-6). Trace midpoints and give the comparison count before declaring not-found.Searching for 2: mid=7 > 2, so search left; then mid
Example 14
easy
Binary search is like looking up a word in a dictionary by opening to the ____.
Example 15
hard
If sorted list length doubles, how does worst-case binary search comparison count change?Doubling n adds exactly one level: log₂(2n)
Example 16
medium
Trace binary search for target =20 in [2,4,6,8,10,12,14,16,18,20] (indices 0-9). List the midpoints visited and the comparison count.Step 1: mid=4 (value 10); 20 > 10 so lo = 5; then mid=7,8,9 → found at index 9 in 4 comparisons
Example 17
medium
Sorted list size n=500. Worst-case binary-search comparisons?
Example 18
medium
On a sorted list of n, what input case gives binary search its best-case (fewest) comparisons?
Example 19
medium
Why is computing the midpoint as `(low + high) / 2` risky for very large indices, and what is the safer form?
Example 20
easy
If the target equals the middle element, what does binary search do?