Binary Search¶

In one sentence

If a yes/no question flips only once as a number grows (yes, yes, …, yes, no, no, …), you can find the flip point by halving the range each time: about \(30\) checks for a range of \(10^9\).

1. What problem does it solve?¶

Example — 1873E · Building an Aquarium (2-BinarySearch · B, 4-Misc · E, rating 1100)

A coral has \(n\) columns with heights \(a_1, \dots, a_n\). You build a tank of height \(h \ge 1\) and fill it with water, so every column shorter than \(h\) gets \(h - a_i\) units of water (taller columns get none). You have at most \(x\) units of water. What is the largest \(h\) you can build?

Limits: \(t \le 10^4\), \(n \le 2 \cdot 10^5\) (sum over tests), \(a_i, x \le 10^9\).

Input              Output
5
7 9
3 1 2 4 6 2 5      4
3 10
1 1 1              4
4 1
1 4 3 4            2
6 1984
2 6 5 9 1 8        335
1 1000000000
1                  1000000001

Computing the answer directly is awkward. Checking a guess is easy. "Is height \(h\) affordable?" is one loop:

\[ \text{water}(h) = \sum_{i=1}^{n} \max(0,\; h - a_i) \;\le\; x . \]

And the answer to that question is monotone. A taller tank never needs less water. So if \(h\) is affordable, every smaller height is too. For the first test (\(x = 9\)):

\(h\)	1	2	3	4	5	6
water	0	1	4	8	13	19
\(\le 9\)?	yes	yes	yes	yes	no	no

We want the last yes. Binary search finds it without trying every \(h\).

2. The math¶

2.1 The invariant¶

Keep a range \([l, r]\) that is guaranteed to contain the answer. Look at the middle, \(mid = \lfloor (l + r) / 2 \rfloor\):

check(mid) is yes: the last yes is at \(mid\) or to its right. Remember \(mid\) as a candidate and search \([mid + 1, r]\).
check(mid) is no: every \(h \ge mid\) is also no, so the last yes is to the left. Search \([l, mid - 1]\).

Each step removes at least half of the range. Starting from \(r - l + 1 = N\) values, after \(s\) steps at most \(N / 2^s\) remain, so the loop ends after about \(\log_2 N\) steps.

range size \(N\)	\(10^5\)	\(2 \cdot 10^9\)	\(10^{18}\)
steps \(\lceil \log_2 N \rceil\)	17	31	60

2.2 How big can the answer be?¶

With \(h = \min(a) + x + 1\), the shortest column alone needs \(x + 1\) units. So the answer is at most \(\min(a) + x\), which is \(10^9 + 10^9\). The last sample has answer \(1000000001 > 10^9\), so the slide template's r = 1000000000 would print \(10^9\) and get Wrong Answer. Always derive r from the constraints.

2.3 Trace on the example¶

\(l = 1\), \(r = \min(a) + x = 1 + 9 = 10\).

\(l\)	\(r\)	\(mid\)	water(\(mid\))	\(\le 9\)?	action	`ans`
1	10	5	13	no	\(r = 4\)	\(-1\)
1	4	2	1	yes	\(l = 3\)	2
3	4	3	4	yes	\(l = 4\)	3
4	4	4	8	yes	\(l = 5\)	4
5	4	—			stop: \(l > r\)	4

2.4 Two kinds of binary search¶

kind	what you search	tool
in a sorted list	"how many elements are \(< x\) / \(\le x\)?", "where would \(x\) go?"	`bisect_left`, `bisect_right`
on the answer	the largest (or smallest) value that works	`while l <= r` + your own `check`

For a sorted list a and a value x:

a = [1, 3, 3, 3, 7]        x = 3
         ^           ^
 bisect_left = 1     bisect_right = 4
 (first index with a[i] >= 3)   (first index with a[i] > 3)

bisect_left(a, x) \(=\) number of elements \(< x\)
bisect_right(a, x) \(=\) number of elements \(\le x\)
number of elements equal to \(x\) \(=\) bisect_right - bisect_left \(= 4 - 1 = 3\)

3. Templates¶

3.1 Binary search on the answer¶

From our slides (USACO Algorithm — From Bronze to Silver, 16 Jan). This version finds the largest valid value, which is exactly what Building an Aquarium needs:

def check(mid):
    # Check if 'mid' is a valid solution
    # Logic depends on the problem
    return True

l = 0
r = 1000000000
ans = -1

while l <= r:
    mid = (l + r) // 2
    if check(mid):
        ans = mid   # Found a valid answer, save it
        l = mid + 1 # Try to find a bigger one
    else:
        r = mid - 1 # Too big, go smaller

print(ans)

To find the smallest valid value instead, swap the two moves: on yes, save ans and go left (r = mid - 1); on no, go right (l = mid + 1).

3.2 `bisect` in a sorted list¶

From our lesson on June 14. The original sheet wrote x where it meant val; that is corrected here.

from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.readline


def solve():
    n, val = map(int, input().split())
    a = list(map(int, input().split()))

    a.sort()

    # number of elements where ai < val
    ans1 = bisect_left(a, val)

    # number of elements where ai <= val
    ans2 = bisect_right(a, val)

    # number of elements where ai > val
    ans3 = len(a) - bisect_right(a, val)

    # number of elements where ai >= val
    ans4 = len(a) - bisect_left(a, val)


t = 1
for _ in range(t):
    solve()

4. Worked solution — Building an Aquarium¶

The slide template with a real check and a correct upper bound. check stops summing as soon as the water exceeds \(x\).

import sys

input = sys.stdin.readline


def solve():
    n, x = map(int, input().split())
    a = list(map(int, input().split()))

    def check(mid):
        water = 0
        for h in a:
            if h < mid:
                water += mid - h
                if water > x:
                    return False
        return True

    l = 1
    r = min(a) + x
    ans = -1

    while l <= r:
        mid = (l + r) // 2
        if check(mid):
            ans = mid
            l = mid + 1
        else:
            r = mid - 1

    print(ans)


t = int(input())
for _ in range(t):
    solve()

Cost: about \(31\) checks of \(O(n)\) each, so \(O(n \log(\min(a) + x))\) per test.

5. How to recognise it¶

Ask yourself: "If I knew the answer \(h\), could I check it quickly? And if \(h\) works, does \(h - 1\) (or \(h + 1\)) also work?"

phrase in the statement	search for	check is
"maximum height / size such that the cost is at most …"	largest yes	"is \(h\) affordable?"
"minimum time / cost such that …"	smallest yes	"is \(T\) enough?"
"how many elements are at most \(v\)" (many queries)	position in a sorted list	`bisect_right`

6. Common mistakes¶

The upper bound is too small

The slide template uses r = 1000000000. In Building an Aquarium the answer can be \(10^9 + 1\) (last sample). Always ask what the largest possible answer is.

Moving the wrong way

For "largest yes", a yes means go right. For "smallest yes", a yes means go left. Trace the loop on a tiny example before submitting.

check is not monotone

If yes/no can flip back and forth, binary search silently returns garbage. Convince yourself that "\(h\) works ⇒ \(h - 1\) works" (or the reverse).

bisect on an unsorted list

bisect_left assumes the list is sorted. Sort once before all queries, not inside the query loop.

while l < r with the template's moves

The template needs l <= r. With l < r, the last candidate is never checked.

7. Practice¶

Problem	Set	Rating	Kind
1873E · Building an Aquarium	2-BinarySearch · B, 4-Misc · E	1100	largest yes (this page)
1850E · Cardboard for Pictures	2-BinarySearch · C, 4-Misc · F	1100	on the answer, watch the upper bound
1676E · Eating Queries	4-Misc · B	1100	sort + prefix sums + `bisect_left`
1840D · Wooden Toy Festival	2-BinarySearch · D	1400	smallest waiting time that works
371C · Hamburgers	3-TwoPointers · F	1600	largest number of burgers
1462F · The Treasure of The Segments	7-Intervals · D	1800	`bisect` on sorted endpoints

Credits & licenses

Section structure follows USACO Guide — Binary Search by Darren Yao, Abutalib Namazov, Andrew Wang, Qi Wang and Dustin Miao, licensed CC BY-NC-SA 4.0.
The templates in §3 are from our slides and lesson sheet (with the x → val typo fixed). Everything else (tables, trace, upper-bound analysis, worked solution, mistakes) is ours.