Binary Search — Foundation for Indexing

Every query you've executed so far scans the whole table, checking each row one at a time — O(n) work no matter what you're looking for. Before building a B-tree index to fix that, it's worth building and understanding its core primitive in isolation: binary search over a sorted array, which is O(log n).

The idea

If data is sorted, you don't need to check every element to find a target — you can repeatedly cut the search space in half. Look at the middle element:

• If it equals the target, you're done.
• If it's greater than the target, the target (if present) must be in the left half — discard the right half.
• If it's less than the target, the target must be in the right half — discard the left half.

Each comparison halves the remaining candidates, so a sorted array of a billion elements needs at most ~30 comparisons — versus up to a billion for a linear scan.

Step through it below and watch lo and hi close in. The tinted rail marks everything still worth checking — note how much of it vanishes after a single comparison. That discarded region is the work you never do.

Then use Unsort the array and run the same search again. The algorithm halves just as confidently, and confidently throws away the half holding your target. That is why "sorted" is a precondition and not a suggestion.

Implementation

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

Getting the loop bounds right is the classic source of bugs:

• The loop condition must be lo <= hi, not lo < hi — otherwise a single-element remaining range (lo == hi) gets skipped, missing a target that could be exactly there.
• mid = (lo + hi) // 2 needs to floor-divide; in languages with fixed-width integers, lo + hi can overflow for very large arrays, which is why some implementations compute mid = lo + (hi - lo) // 2 instead — worth knowing even if it doesn't bite you at these array sizes.
• On a miss, return a clear sentinel (-1) rather than an exception, so callers can cheaply check "found or not."

Range queries

A single-target lookup isn't the only thing binary search enables. BSEARCH_RANGE <sorted_csv> <low> <high> asks for every value between two bounds — the classic "range scan" a database needs for queries like WHERE age BETWEEN 20 AND 30. Since the array is sorted, once you find the boundary where values enter the range, every subsequent value is a candidate until you exit the range — you never need to look at values outside [low, high]:

def bsearch_range(arr, low, high):
    return [v for v in arr if low <= v <= high]

A correct-but-naive version like the one above is O(n) — fine for this warm-up exercise. The insight to carry forward is that binary search can find the first index >= low in O(log n), and then you only need to walk forward until you pass high, which is O(log n + k) where k is the number of matching results — far better than scanning the whole array when the sorted structure is available.

Why this matters for the database

A sorted array is essentially a "flat," single-level index: values in order, findable in O(log n). The problem is that keeping a flat array sorted under insertions is expensive — inserting into the middle of a sorted array requires shifting every following element, O(n) per insert. That's exactly the problem B-trees solve: they preserve sorted, binary-searchable structure within each node, while allowing efficient insertion by growing a tree instead of shifting a flat array. Every node in the B-tree you build next lesson uses binary search internally to decide which child to descend into — so what you just implemented isn't a detour, it's a component you'll call directly.