Binary Search

Binary Search | Algoryva

First, the naive way

Scan from the left

To find target in a sorted array, the direct way checks elements one by one until it finds the target or runs out.

This ignores the most valuable fact we have: the array is sorted. If a[5] is already bigger than the target, nothing to its right can match, yet a scan that does not use ordering keeps going.

python

def linear_search(a, target):
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1

Cost: O(n) per search. With 10^6 elements and 10^6 searches that is 10^12 steps.

Worked by hand

Trace by hand

Search for 11 in [1, 3, 5, 7, 9, 11, 13, 15] (indices 0 to 7).

step	lo	hi	mid	a[mid]	decision
1	0	7	3	7	7 < 11, so lo = 4
2	4	7	5	11	found at index 5

1
Pick the middle
mid = (0 + 7) // 2 = 3, so a[3] = 7. Too small, so indices 0 to 3 are ruled out.
2
Repeat on what is left
lo = 4, hi = 7: mid = 5, a[5] = 11. Match. Two looks instead of six.

Implementation

Lower bound: the one template to master

The most useful form returns the first index whose value is ≥ target (or len(a) if none). It handles present values, absent values and duplicates in one shape, so learn this one well.

The invariant is what keeps you safe: *the answer is always in [lo, hi]*, where hi is exclusive-friendly (hi = len(a) is a legal answer meaning “none”).

Plan in plain steps

pseudocode

lo = 0, hi = n
while lo < hi:
    mid = middle of lo and hi
    if a[mid] < target: the answer is right of mid -> lo = mid + 1
    else: mid could be the answer -> hi = mid
return lo

python

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(a, target):        # first index with value > target
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 2, 2, 2, 5, 8]
print(lower_bound(a, 2))   # 1
print(upper_bound(a, 2))   # 4
print(upper_bound(a, 2) - lower_bound(a, 2))   # 3

Reading the code

›hi = len(a) (not len(a) - 1) because “every element is smaller” must be representable: the answer is then len(a).
›When a[mid] < target, mid itself is too small, so lo = mid + 1 strictly shrinks the region. When not, mid might be the answer, so hi = mid keeps it. Both branches shrink the range, so the loop always ends.
›The loop ends when lo == hi: a single position remains, and that is the first index that is not too small.
›upper_bound differs only by <=. The number of copies of a value is upper_bound − lower_bound.
›Python ships this as bisect.bisect_left and bisect.bisect_right. Use them in contests; write your own to understand them.

Implementation

Binary search on the answer

The array was never the point: what matters is a yes/no question that flips exactly once. If “is x big enough?” is false for small x and true from some point on, you can binary search x itself, with no array at all.

Example: a shop must cut k or more pieces of length L from ropes of given lengths. What is the longest L that works? Bigger L means fewer pieces, so “can we get k pieces of length L?” is true for small L, then false forever. Search for the last true.

python

def max_piece_length(ropes, k):
    def ok(L):                      # can we cut at least k pieces of length L?
        return sum(r // L for r in ropes) >= k
    lo, hi = 1, max(ropes)          # invariant: answer in [lo - 1, hi]; lo - 1 is 0 when nothing works
    best = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if ok(mid):
            best = mid
            lo = mid + 1            # try longer
        else:
            hi = mid - 1
    return best

print(max_piece_length([8, 5, 12], 6))   # 4

Reading the code

›ok is the whole problem-specific part. It must be monotonic: once it flips, it never flips back.
›We record best whenever ok is true and then look for something bigger; when ok is false we look smaller.
›This loop uses inclusive bounds (lo <= hi), a second common style. Pick one style and stick to it in a solution; mixing them is where bugs breed.
›Cost: log(max) calls of ok, each O(n), so O(n log max).

Worked problem

Integer square root

The problem

Given a non-negative integer n, return the largest integer x with x * x <= n, without using a square-root function.

The check x * x <= n is true for small x and false from some point: monotonic, so we can search x.
Search range: 0 to n (and n itself works for n <= 1).
When the check is true, remember x and try bigger; otherwise go smaller.

python

def isqrt(n):
    lo, hi, best = 0, n, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            best = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return best

print(isqrt(17))   # 4
print(isqrt(16))   # 4
print(isqrt(0))   # 0

Takeaway. No array here at all: binary search works on any monotonic yes/no question. That is the most powerful form of the idea.

Worked problem

First bad version

The problem

Versions 1..n were released; from some version on, every version is bad. You can ask is_bad(v). Find the first bad version using as few calls as possible.

is_bad is false, false, …, true, true: one flip, so monotonic.
We want the first true, exactly what lower_bound finds.
Keep hi = mid when bad (it could be the first) and lo = mid + 1 when good.

python

def first_bad(n, is_bad):
    lo, hi = 1, n
    while lo < hi:
        mid = (lo + hi) // 2
        if is_bad(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(first_bad(10, lambda v: v >= 7))   # 7

Takeaway. “First time something becomes true” is lower bound on a predicate. It needs about log₂ n calls instead of n.

Wrap-up

Remember this

Sorted order lets one comparison discard half of the candidates, giving O(log n).
Lower bound (first index ≥ x) is the template to master; it handles misses and duplicates.
Keep an invariant about where the answer lies, and make every branch shrink the range.
The array is optional: any monotonic yes/no question can be binary searched.
Spot it by “minimise the maximum”, “maximise the minimum”, or a huge answer range with a cheap check.

Cheat sheet

Lower bound (first ≥ x): lo, hi = 0, n; a[mid] < x → lo = mid + 1 else hi = mid
Count of x: upper_bound(x) − lower_bound(x)
Search on answer: check(x) monotonic → binary search x
Cost: O(log n) per search; O(log R × check) on answers
Python: bisect_left / bisect_right
Needs: sorted data or a monotonic predicate

Top traps to avoid

Setting lo = mid or hi = mid in a way that does not shrink the range.
Binary searching unsorted data.
Non-monotonic check in “search on the answer”.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.About how many comparisons does binary search need for 1,000,000 sorted items?
2.For a = [1, 2, 2, 2, 5, 8], what does lower_bound(a, 2) return?
3.In lower bound, why is hi initialised to len(a) instead of len(a) - 1?
4.Which problem is a good fit for “binary search on the answer”?
5.What goes wrong with lo = mid (no +1) in a while lo < hi loop where mid = (lo + hi) // 2?
6.isqrt(17) with the search from the lesson returns:
7.What does bisect.bisect_left([1, 2, 2, 2, 3], 2) return?
8.What does bisect.bisect_right([1, 2, 2, 2, 3], 2) return?
9.Using this loop on a = [1, 3, 5, 5, 7] to find the first index with value >= 5, what is lo at the end? lo, hi = 0, len(a) while lo < hi: m = (lo+hi)//2; if a[m] < 5: lo = m+1 else: hi = m
10.Binary search on the answer: what is the smallest integer x with x*x >= 50?
11.Binary search on the answer needs which property of the check?
12.What is the worst-case number of comparisons for binary search over n sorted values?
13.Why is lo + (hi - lo) // 2 preferred to (lo + hi) // 2 in languages with fixed-width integers?
14.In a sorted list [2, 4, 10, 10, 11], how many values are <= 10?
15.In while lo < hi with hi = m, which update avoids an infinite loop?

Binary Search

After this lesson you will be able to

Builds on

Unlocks

The guessing game

Scan from the left

One comparison against the middle removes half

What binary search really needs

Watch the region shrink

What a miss looks like

Trace by hand

Lower bound: the one template to master

Reading the code

Binary search on the answer

Reading the code

Why it is logarithmic

Edge cases

Mistakes to avoid

How to spot binary search

Integer square root

First bad version

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core31 problems

Application24 problems

Challenge2 problems