Start with the recap, study the fully worked examples, then use the practice problems to
check your understanding of Binary Search.
This page combines explanation, solved examples, and follow-up practice so you can move
from recognition to confident problem-solving in CS Thinking.
Concept Recap
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.
Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.
What to Focus On
Core idea:Each comparison eliminates half the remaining possibilities — O(log n) vs O(n) for linear search.
Common stuck point:Binary search only works on sorted data — applying it to unsorted data gives wrong results.
Sense of Study hint:To perform binary search, set low = 0 and high = length - 1. Compute mid = (low + high) / 2. If the target equals the middle element, you are done. If the target is less, set high = mid - 1. If greater, set low = mid + 1. Repeat until found or low > high.
Worked Examples
Example 1
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
Answer
4 comparisons; mids 4,7,8,9
First step
1
low=0, high=9, mid=4 (value 10). 20>10, low=5.
See the full worked solution + why-it-works coaching
Setup·Key insight·Why it works·Common pitfall·Connection
Trace binary search for target =4 in [2,4,6,8,10,12,14,16,18,20] (indices 0-9). Midpoints and comparison count.
Example 3
medium
Trace binary search for target =1 in [1,3,5,7,9,11,13,15,17,19] (indices 0-9). Midpoints and comparison count.
Example 4
hard
You want to find the FIRST occurrence of a duplicated value in a sorted list. Why does plain binary search fail, and how do you adapt it?
Example 5
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 6
hard
Write pseudocode for an iterative binary search returning the index, or −1 if not found.
Example 7
challenge
Prove that binary search makes at most ⌈log2(n+1)⌉ comparisons by induction on the size of the search range.
Practice Problems
Try these problems on your own first, then open the solution to compare your method.
Example 1
easy
Binary search requires the list to be in what state?
Example 2
easy
What is the time complexity of binary search?
Example 3
easy
In a sorted list, you compare the target to the middle and the target is smaller. Search which half?Target < mid (7): discard right half, new hi = mid − 1 = 2
Example 4
easy
Roughly how many comparisons does binary search need for a sorted list of 1000 items (worst case)?
Example 5
easy
Binary search is like looking up a word in a dictionary by opening to the ____.
Example 6
easy
If the target equals the middle element, what does binary search do?
Example 7
easy
A larger target than the middle element means search which half?Target > mid (7): discard left half, new lo = mid + 1 = 4
Example 8
easy
Is binary search faster than linear search on a large sorted list?
Example 9
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 10
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 11
medium
For n=64, how many comparisons does binary search need in the worst case?Each comparison halves the range: 64 → 32 → 16 → 8 → 4 → 2 → 1 (6 steps)
Example 12
medium
Why is computing the midpoint as `(low + high) / 2` risky for very large indices, and what is the safer form?
Example 13
medium
Binary search vs linear search on n=1,000,000 sorted items: worst-case comparison counts?
Example 14
medium
After a comparison, your code sets `high = mid` instead of `mid - 1` and the range never shrinks past one element. What bug can occur?
Example 15
medium
On a sorted list of n, what input case gives binary search its best-case (fewest) comparisons?
Example 16
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 17
medium
For n=128, give the exact worst-case number of binary-search comparisons.128 → 64 → 32 → 16 → 8 → 4 → 2 → 1 is exactly 7 halvings
Example 18
challenge
Prove binary search makes at most ⌈log2n⌉+1 comparisons. Outline the halving argument.
Example 19
challenge
Binary search can find the smallest x with x2≥50 over integers 1..100. What is x, and why does binary search apply to a non-list problem?
Example 20
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 21
easy
True or false: binary search works on an unsorted list.
Example 22
easy
On a sorted list of 16 items, worst-case binary-search comparisons?16 → 8 → 4 → 2 → 1: ⌈log₂ 16⌉ + 1 = 5 worst-case comparisons
Example 23
easy
When target < middle element, which boundary updates and how?Target < mid (7): set high = mid − 1 = 2; search continues in left half only
Example 24
easy
When target > middle element, which boundary updates and how?Target > mid (7): set low = mid + 1 = 4; search continues in right half only
Example 25
easy
What is the BEST-case number of comparisons for binary search?
Trace binary search for target =15 in [2,4,6,8,10,12,14,16,18,20] (indices 0-9). Comparison count and result.Search for 15: mid=10, then 16, 12, 14 — window collapses after 4 comparisons; not found
Example 28
medium
On a sorted list of 1024 items, the worst-case binary search comparison count?1024 → 512 → … → 1: 10 halvings + 1 boundary check = 11 worst-case comparisons
Example 29
medium
Linear search vs binary search on n=65,536. Worst-case comparison counts?
Example 30
medium
Why is sorting first and then binary-searching often slower than a single linear search for a one-off lookup?
Example 31
medium
Sorted list size n=500. Worst-case binary-search comparisons?
Example 32
medium
An off-by-one bug uses high=mid instead of high=mid−1. When does it fail catastrophically?
Example 33
medium
Compare integer overflow risk of (low+high)/2 vs low+(high−low)/2. In what scenario does the first overflow?
Example 34
medium
If you're allowed 20 binary-search comparisons, what is the largest sorted list you can search?20 halvings: each comparison doubles the searchable size; 2^20 = 1,048,576 items
Example 35
medium
Sorted list of 50 items, worst-case binary-search comparisons?
Example 36
hard
Binary search finds the smallest integer x such that x3≥100 over 1≤x≤100. What is x?
Example 37
hard
A student tries binary search on [3,1,5,2,7] for target 5. What is the result, and why?
Example 38
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 39
hard
You binary-search a list of 1 billion sorted items. Roughly how many comparisons worst-case?
Example 40
challenge
Binary search a rotated sorted array (e.g., [6,7,8,1,2,3,4,5]). What single observation makes a O(logn) search still possible?