Skip to main content
CodeFlow
algorithms~14 minRoute 03 1 of 1

Binary Search

How halving wins — log time made visible.

Prerequisites:Conditions & Booleans

Story — guess my number

1005025136each step halves the work

I'm thinking of a number between 1 and 100. You guess; I tell you higher, lower, or got it. What's your strategy?

Smart players don't guess 1, then 2, then 3 — that's a linear search and it could take 100 guesses. They guess 50, slicing the range in half. Then 25 or 75. Then half again. In seven guesses, you can pinpoint any number from 1 to 100. That is binary search.

Halver says

Each comparison cuts the work in half. Sorted data + middle index = log time. The catch: the array must be sorted, or every guess is a gamble.

See it — half goes dark each step

Pick a target. Press Step. Watch which half gets crossed out — those values can't possibly hold your target, so the algorithm forgets about them entirely.

  1. 03
  2. 17
  3. 211
  4. 318
  5. 424
  6. 531
  7. 642
  8. 755
  9. 863
  10. 978
  11. 1084
  12. 1191
  13. 1299

Searching 13 items for 42. Press Step to compare with the middle.

low=0 · high=12 · steps=0

✎ Sharpen your pencil

After watching a few searches, write one sentence describing what "low" and "high" represent — without using the word "index".

Halver says

Watch the greyed-out cells. Those are values I will never look at again — I proved they cannot hold the target.

Try it — count the steps

Exercise. Imagine a sorted list of 1,000,000 entries. Without using a calculator, what's the maximum number of comparisons binary search needs?

Reveal answer

Each step halves the list, so the question is: how many times can you halve a million before you reach 1? 1,000,000 → 500,000 → 250,000 → … 2 → 1 takes about 20 halvings. That's log₂(1,000,000) ≈ 20. Twenty comparisons to find a needle in a million-item haystack.

Code it — five languages, one halving

The shape is identical everywhere: two pointers (low and high), a middle, a three-way comparison, and shrink one side. The only per-language wrinkle is integer overflow when adding low and high — Java and C++ use low + (high - low) / 2 to stay safe.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Walk through it line by line

Step 1 / 4python
1arr = [3, 7, 11, 18, 24, 31, 42, 55, 63, 78, 84, 91, 99]
2target = 42
3low, high = 0, 12
4mid = (low + high) // 2  # 6
5arr[mid]  # 42 — found at index 6

Halver says

In Java and C++, write `low + (high - low) / 2` instead of `(low + high) / 2` — for huge arrays, the simple sum can overflow Int.MAX_VALUE.

Quiz it — make it stick

  1. Question 1

    Linear search on a 1,000,000-item list takes up to 1,000,000 comparisons. About how many does binary search take in the worst case?

  2. True or false — Question 2

    Binary search works on any array.

  3. Predict — Question 3

    How many comparisons to find 78 in [3, 7, 11, 18, 24, 31, 42, 55, 63, 78, 84, 91, 99]?

    # Walk binary search by hand:
# step 1: mid=6, arr[6]=42 < 78 → low=7
# step 2: mid=10, arr[10]=84 > 78 → high=9
# step 3: mid=8, arr[8]=63 < 78 → low=9
# step 4: mid=9, arr[9]=78 → found

No Dumb Questions

Real questions other learners asked on this page.

  • What if the array has duplicates?
    Plain binary search returns *some* matching index, not necessarily the first or last. If you need leftmost or rightmost, you tweak the comparison: keep moving "high = mid" (not mid - 1) when you find a match, and keep going until low == high. That gives you the first occurrence.
  • When is linear search actually better?
    When the array is unsorted (binary search just won't work), when it's tiny (10 items — overhead beats halving), or when you're going to scan everything anyway. Binary search wins on big sorted lookups; that's its niche.
  • Why use `(low + high) / 2` and not `(high - low) / 2`?
    Because we want the midpoint — halfway between low and high, not half the distance. The version `low + (high - low) / 2` is mathematically the same as `(low + high) / 2`, but it avoids overflowing when low + high exceeds the integer maximum (a real bug Joshua Bloch wrote about for Java's Arrays.binarySearch).