Unit 5: Cut It In Half

Halving beats walking, and it is not close

Guess a number between 1 and 100. Guess the middle, hear "higher" or "lower", and throw away half the numbers each time.

Six guesses here. A billion numbers would take thirty.

Python

secret = 73
low = 1
high = 100
steps = 0

while low <= high:
    mid = (low + high) // 2
    steps += 1
    if mid == secret:
        break
    if mid < secret:
        low = mid + 1
    else:
        high = mid - 1

print(mid, steps)

It prints

73 6

The same loop, on a sorted list

The list is sorted, so the middle item tells you which half the target could be in. Keep two ends and pull them together.

Return the position when you land on it, and -1 when the ends cross without a hit.

Python

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

numbers = [2, 4, 8, 15, 16, 23, 42]
print(find(numbers, 15), find(numbers, 5))

It prints

3 -1

How many halvings a list can take

Each guess halves what is left, so the number of guesses is log2 n — rounded up. It grows so slowly that the size of the list barely matters.

One warning that costs people whole contests: mid + 1 and mid - 1 must be there. Without them the ends stop moving and the loop never finishes.

Python

import math

for n in [100, 1000000, 1000000000]:
    print(n, math.floor(math.log2(n)) + 1)

It prints

100 7
1000000 20
1000000000 30

Usually you do not want an exact match

Real questions sound like "how many are under 50?" or "where would 7 go?". Those want the first position holding something not smaller than the target — its lower bound.

The loop is subtly different: low < high, and high starts one past the end because the answer may be "off the end".

Python

def lower_bound(numbers, target):
    low = 0
    high = len(numbers)
    while low < high:
        mid = (low + high) // 2
        if numbers[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

numbers = [1, 3, 3, 3, 7, 9]
print(lower_bound(numbers, 3), lower_bound(numbers, 4), lower_bound(numbers, 10))

It prints

1 4 6

Why high = mid and not mid - 1

The item at mid might be the answer, so it must stay inside the range. That is exactly why this version never uses <=: with high = mid, a low <= high loop would spin for ever.

Hold the meaning steady instead of memorising the punctuation: everything before low is too small, everything from high on is not.

Two lower bounds count anything you like

How many 3s are in the list? The first position of a 3, subtracted from the first position of a 4. Two binary searches, no counting.

The same subtraction gives "how many are between 3 and 8" and every question shaped like it.

Python

def lower_bound(numbers, target):
    low = 0
    high = len(numbers)
    while low < high:
        mid = (low + high) // 2
        if numbers[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

numbers = [1, 3, 3, 3, 7, 9]
print(lower_bound(numbers, 4) - lower_bound(numbers, 3))
print(lower_bound(numbers, 8) - lower_bound(numbers, 3))

It prints

3
4

And now you may use the library

Python ships this as bisect. bisect_left is the lower bound you just wrote; bisect_right is the first position past the last equal item.

Use it in a contest — but only now that you know what it does, because when a problem needs a lower bound over something that is not a list, you will have to write the loop again.

Python

import bisect

numbers = [1, 3, 3, 3, 7, 9]
print(bisect.bisect_left(numbers, 3), bisect.bisect_right(numbers, 3))
print(bisect.bisect_right(numbers, 3) - bisect.bisect_left(numbers, 3))

It prints

1 4
3

Nothing is sorted, and there is no list

Three planks of wood, 7cm, 9cm and 3cm. Cut them into pieces that are all the same whole number of centimetres, and give one piece to each of four friends. Waste is allowed.

How long can each piece be? There is no list to search — but the answer is a number, and the answers behave themselves.

The question that flips exactly once

Ask: "can I get 4 pieces of length L?" Length 1 — easily. Length 3 — yes, six pieces. Length 4 — only three. Length 5 and up — no.

Yes, yes, yes, no, no, no. It flips once and never flips back, and that is all binary search has ever needed.

Python

planks = [7, 9, 3]

def pieces(length):
    return sum(p // length for p in planks)

for length in range(1, 10):
    print(length, pieces(length), pieces(length) >= 4)

It prints

1 19 True
2 8 True
3 6 True
4 3 False
5 2 False
6 2 False
7 2 False
8 1 False
9 1 False

So binary search the length

Low is 1, high is the longest plank. Test the middle: if it works, remember it and try longer; if not, go shorter.

The answer is 3. Thirty tests would handle planks a billion centimetres long.

Python

planks = [7, 9, 3]
friends = 4

def pieces(length):
    return sum(p // length for p in planks)

low = 1
high = max(planks)
best = 0
while low <= high:
    mid = (low + high) // 2
    if pieces(mid) >= friends:
        best = mid
        low = mid + 1
    else:
        high = mid - 1

print(best)

It prints

3

The one thing that has to be true

The yes/no question must be monotone: once it turns from yes to no, it can never go back to yes.

Here it holds because shorter pieces can only be easier to cut. If your question wobbles — yes, no, yes — binary search will confidently return nonsense, and it will look right on your own small example.

Forty numbers is too many to try

Back to subset sums, but with 40 numbers instead of 20. Trying every subset is 2 ** 40 — about a million million. Out of reach.

But 2 ** 20 is only a million, and it is reachable twice.

Cut the list in half and list both sides

Every subset of the whole list is some subset of the left half plus some subset of the right half. So build all the sums of each half separately.

Ten numbers: 1024 subsets in total, but only 32 and 32 to list.

Python

numbers = [3, 34, 4, 12, 5, 2, 9, 14, 7, 6]

def sums(part):
    result = []
    for mask in range(1 << len(part)):
        total = 0
        for i in range(len(part)):
            if (mask >> i) & 1:
                total += part[i]
        result.append(total)
    return result

first = sums(numbers[:5])
second = sums(numbers[5:])
print(len(first), len(second), 1 << 10)

It prints

32 32 1024

Then join the halves with a binary search

Sort the second half's sums. Now for each sum s from the first half, ask whether target - s is in the sorted pile — one binary search each.

So the cost is 2 20 to build, plus 2 20 binary searches. Millions instead of millions of millions.

Python

numbers = [3, 34, 4, 12, 5, 2, 9, 14, 7, 6]

def sums(part):
    result = []
    for mask in range(1 << len(part)):
        total = 0
        for i in range(len(part)):
            if (mask >> i) & 1:
                total += part[i]
        result.append(total)
    return result

def contains(values, wanted):
    low = 0
    high = len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == wanted:
            return True
        if values[mid] < wanted:
            low = mid + 1
        else:
            high = mid - 1
    return False

first = sums(numbers[:5])
second = sorted(sums(numbers[5:]))

def reachable(target):
    for s in first:
        if contains(second, target - s):
            return True
    return False

print(reachable(41), reachable(95), reachable(96))

It prints

True False True

Why 95 is out of reach

The ten numbers add up to 96. Reaching 95 would mean leaving out exactly 1 — and there is no 1 to leave out.

Worth noticing because it is a check you can do by hand, on a program whose answer you otherwise have to trust.