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.
Looking up a word in a dictionary: open to the middle, then go left or right depending on where your word falls.
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 = index 3 = 7, match on first comparison
Example 5
hard
A student tries binary search on [3,1,5,2,7] for target 5. What is the result, and why?
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=3 > 2, then mid=1 < 2, range empty — 3 comparisons, not found
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) = log₂ n + 1
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?