Pebellslearn by building
0%
RoadmapMatrixCatalogSandboxSign in
Recursion, Searching & Sorting  ›  Lesson

Binary Search & Library Search

Binary Search 22 minFind anything in sorted data by halving the range every step
You're building a piece ofTunebox — search & charts
This piece — find_track(): Finds a title in a sorted library in a handful of steps.
Scenario The library view keeps every title sorted A→Z, so typing a name doesn't scan 50,000 songs — binary search opens the middle and halves the range, finding any track in about 16 looks.
Your task
Build find_track(sorted_titles, title). The titles are sorted A→Z. Use binary search — keep a low and high bound, compare the middle title, and halve the range — to return the index of `title`, or -1 if it isn't in the library. Example: find_track(["a", "c", "e", "g"], "e") → 2.

Binary Search & Library Search

A Tunebox library holds 50,000 titles, sorted A→Z. Checking them one by one means up to 50,000 comparisons for a title that isn't there. Binary search opens the library in the middle, sees which half the title must be in, and throws the other half away — 16 looks, at most, for all 50,000.

Halving the search space

Linear search works on anything. Binary search needs one thing in return: the data must be sorted, so a single comparison tells you which side to keep.

python

Each look halves what's left, so the number of looks is how many times you can halve n before nothing remains — about log₂ n:

What does this print?
n, looks = 1_000_000, 0
while n > 0:
    n //= 2
    looks += 1
print(looks)

The invariant that keeps it honest

Binary search is short, and famously easy to get subtly wrong. The cure is to say out loud what lo and hi mean, and keep it true every step:

Invariant: if title is anywhere in the list, it is at an index in lo..hi (both ends included).

  • Start: lo = 0, hi = len - 1 — the whole list, so it's true.
  • titles[mid] < title → the title can't be at mid or left of it: lo = mid + 1.
  • titles[mid] > title → it can't be at mid or right of it: hi = mid - 1.
  • When lo > hi the range is empty — and by the invariant, the title isn't there.
step through it
1titles = ["Aria", "Blue", "Cove", "Dawn", "Echo"]
2lo, hi = 0, len(titles) - 1
3found = -1
4while lo <= hi:
5 mid = (lo + hi) // 2
6 if titles[mid] == "Dawn":
7 found = mid
8 break
9 if titles[mid] < "Dawn":
10 lo = mid + 1
11 else:
12 hi = mid - 1
13print(found)

Watch lo and hi close in: the range is 0..4, then 3..4, then mid lands on "Dawn".

Off-by-one: the classic bugs

Almost every broken binary search breaks the invariant at one of three spots:

bug what happens
while lo < hi with an inclusive hi the last candidate (lo == hi) is never checked
hi = mid with an inclusive hi mid stays in range forever — an infinite loop
lo = mid instead of mid + 1 when hi == lo + 1, mid == lo and nothing moves

Here is the first one. It looks right, and fails on the last title:

broken — fix it

This should print 2, the index of "Cove". It prints -1 — the search gives up while one title is still unchecked.

❓ Cross-question — "Why (lo + hi) // 2 and not / 2?" / always gives a float, and titles[2.0] raises TypeError. // floors to an int.

Coming from Java/JS: you may have learned lo + (hi - lo) / 2 to dodge integer overflow. Python ints never overflow, so (lo + hi) // 2 is safe. In JS remember Math.floor — (lo + hi) / 2 is a float there too.

Lower and upper bound

"Is it there?" is only one question. With duplicates — say, play counts — the useful questions are where does 20 start? and where does it end?

  • lower bound: the first index whose value is >= x
  • upper bound: the first index whose value is > x

These use a half-open range [lo, hi) — hi = len(a), because the answer may be "past the end":

python

Here hi = mid is correct, not a bug — the range is half-open, so mid stays a candidate and the loop still shrinks, because mid < hi always.

The bisect module

Python ships both bounds, written in C:

python
What does this print?
from bisect import bisect_left
titles = ["Aria", "Cove", "Echo"]
print(bisect_left(titles, "Dawn"))

❓ Cross-question — "Can I bisect a list of track dicts by title?" Since Python 3.10, yes: bisect_left(tracks, "Dawn", key=lambda t: t["title"]). The list must already be sorted by that same key.

Binary search on the answer

The same halving works when there is no list at all — only a range of possible answers and a yes/no test that flips once. Tunebox shows album covers in a square grid: with 50 covers, what's the biggest full square?

python

"Does mid fit?" is yes, yes, yes, … no, no as mid grows — that single flip is all binary search needs. When you move lo = mid (keeping mid), round mid up: with lo = 3, hi = 4, rounding down picks 3 again and loops forever.

operation time
linear search O(n)
binary search, lower / upper bound O(log n)
bisect_left, bisect_right O(log n)
insort O(n) — finding the spot is O(log n), shifting the list is O(n)
search on an answer range of size R O(log R × cost of one yes/no test)

Idioms & real-world patterns

Count and range queries with two bisects

How many tracks have between 15 and 30 plays? Two bounds, one subtraction:

python

Bucket a value into ranges

bisect on a list of cut-offs turns a number into a band, with no if chain:

python

⚡ Advanced — "first bad version"

Binary search finds the first True in any monotone yes/no sequence — the first build where a bug appeared, the first day a track crossed a million plays. Make the question a function and search the indexes:

python

Every binary search in this lesson is this one function with a different test.

🎯 Your turn

Write find_track(sorted_titles, title). sorted_titles is sorted A→Z; return the index of title using binary search, or -1 if it isn't there:

  • find_track(["a", "c", "e", "g"], "e") → 2
  • find_track(["a", "c", "e"], "b") → -1

Hint — keep lo and hi inclusive, loop while lo <= hi, and move past mid with mid + 1 / mid - 1.

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upIs it in the library?

Write in_library(sorted_titles, title) returning True if title is in the A→Z-sorted list and False otherwise. Use bisect.bisect_left rather than in.

bisectbinary-search
DrillWhere does it slot in?

Write chart_slot(sorted_plays, plays) by hand (no bisect). sorted_plays is sorted low→high. Return the index where a track with plays plays would be inserted to keep the list sorted, before any equal values. chart_slot([10, 20, 20, 30], 20) → 1.

binary-searchlower-bound
BuildTracks in a play range

Write count_between(sorted_plays, low, high) returning how many values in the sorted list fall in low..high, both ends included, in O(log n). If low > high, return 0.

bisectlower-bound
BossSmallest daily listening cap

A listening queue minutes (track lengths) must be played in order, finishing within days days, and a track can't be split across two days. Write min_daily_cap(minutes, days) returning the smallest number of minutes per day that makes that possible. days is at least 1; an empty queue needs a cap of 0. min_daily_cap([7, 2, 5, 10, 8], 2) → 18 (days of 7+2+5 and 10+8).

binary-searchsearching
CapstoneSearch the rotated wheel

Tunebox's A→Z wheel remembers where you stopped scrolling, so the library can arrive rotated: a sorted list of distinct titles cut at some point, with the back part moved to the front — e.g. ["Fern", "Glow", "Aria", "Blue", "Cove", "Dawn"]. Write find_rotated(titles, title) returning the index of title in O(log n), or -1. The list might not be rotated at all.

binary-searchsearchingconditionals
find_track.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
find_track(sorted_titles, title) → intThe index of the title, found by binary search — or -1 if it's missing.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.