Binary Search Examples: 47 Problems with Answers

Worked examples of Binary Search to try before you open each solution, then practice problems with answers.

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.
Show solution

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

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

medium
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 ⌈log⁡2(n+1)⌉ comparisons by induction on the size of the search range.

Practice Problems

Try each one, 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?

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?

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?

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.

Example 11

medium
For n=64, how many comparisons does binary search need in the worst case?

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.

Example 17

medium
For n=128, give the exact worst-case number of binary-search comparisons.

Example 18

challenge
Prove binary search makes at most ⌈log⁡2n⌉+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?

Example 23

easy
When target < middle element, which boundary updates and how?

Example 24

easy
When target > middle element, which boundary updates and how?

Example 25

easy
What is the BEST-case number of comparisons for binary search?

Example 26

easy
Sorted list of 256 items, worst-case comparisons?

Example 27

medium
Trace binary search for target =15 in [2,4,6,8,10,12,14,16,18,20] (indices 0-9). Comparison count and result.

Example 28

medium
On a sorted list of 1024 items, the worst-case binary search comparison count?

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?

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?

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(log⁡n) search still possible?

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.

Ask yourself: Is the data sorted by the value you want, so each check of the middle can rule out half?

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.

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.

Read the full lesson on Binary Search

Background knowledge

These ideas may be useful before you work through the harder examples.

searchingarrayefficiency