Searching: Linear vs Binary

15 min 35 XP

Study loop Read Predict Run Tweak Prove Review

Lesson 2 of 5 · View course roadmap

Step 1

Learn the idea

How do you find one value among a hundred? Two classic answers:

Linear search — check every item front to back. Simple, works on anything, needs up to n checks.

Binary search — needs sorted data, and it's a superpower: look at the middle, decide which half the target is in, throw the other half away. Repeat.

100 items → at most 7 checks
1,000,000 items → at most 20 checks
Each step: mid = (low + high) // 2, then move low or high

Halving beats scanning by absurd margins, and "can I halve this?" is one of the most valuable questions in all of programming — it's how databases find rows and how git bisect finds the commit that broke everything.

Where you'll use this

Database indexes, autocomplete, DNS resolution and git bisect all live on binary search. 'Can I halve this?' is the question behind almost every system that answers instantly at scale.

Common mistakes

Running binary search on unsorted data — it silently returns nonsense rather than erroring.
Writing while low < high instead of low <= high and missing the last candidate.
Forgetting the +1/-1 when moving low or high, which loops forever on some targets.

Pro tip

Python ships binary search as the bisect module: bisect.bisect_left(sorted_list, target) — use it in real code, write it by hand in interviews.

Step 2

Try it yourself

Blank · autosaved

The lesson example is loaded and ready — press Run, then change something and run it again. Breaking it is part of learning. Want a clean slate? Tap “New blank”.

PYexample.py

⌘ + Enter to run

Output appears here…

Step 3

Pass the challenge +35 XP

Blank · autosaved

Binary-search for 87 in list(range(1, 101)), counting the loop passes. Print Found 87 in N steps, then Linear search: M steps where M is how many checks a front-to-back scan would need (position + 1).

Target output

Found 87 in 7 steps
Linear search: 87 steps

PYchallenge.py

numbers = list(range(1, 101))
target = 87

low, high = 0, len(numbers) - 1
steps = 0
while low <= high:
    steps += 1
    mid = (low + high) // 2
    if numbers[mid] == target:
        print(f"Found {target} in {steps} steps")
        break
    elif numbers[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print(f"Linear search: {numbers.index(target) + 1} steps")

Run your code to check it…

Step 4

Check your understanding

1. What does binary search require that linear search doesn't? A bigger list Sorted data A dictionary Recursion

2. Roughly how many checks does binary search need for 1,000,000 items? ~500,000 ~1,000 ~20 ~2

Last step

Your notes (saved on this device)

Tip: use ← and → to move between lessons, ⌘K to search everything.