Resources

Note that the video above covers both binary search modules.

Please check the Binary Search module for additional resources (though they cover additional material not part of this module).

Introduction

Example - Counting Haybales

Explanation

As each of the points are in the range $0 \ldots 1\,000\,000\,000$, storing locations of haybales in a boolean array and then taking prefix sums of that would take too much time and memory.

Instead, let's place all of the locations of the haybales into a list and sort it. Now we can use binary search to count both the number of haybales with position at most $B$ and the number of haybales with position less than $A$ in $\mathcal{O}(\log N)$ time, and then subtract these two quantities to get the final answer.

Implementation (Without Built-in Functions)

Time Complexity: $\mathcal{O}((N + Q) \log{N})$

Copy
def at_most(x: int) -> int:
	lo = 0
	hi = len(bales)
	while lo < hi:
		mid = (lo + hi) // 2
		if bales[mid] <= x:
			lo = mid + 1
		else:
			hi = mid
	return lo

Implementation (With Built-in Functions)

Time Complexity: $\mathcal{O}((N + Q) \log{N})$

Copy
from bisect import bisect

inp = open("haybales.in", "r")
out = open("haybales.out", "w")

bale_num, query_num = map(int, inp.readline().split())
bales = sorted(list(map(int, inp.readline().split())))
for _ in range(query_num):
	start, end = map(int, inp.readline().split())
	print(bisect(bales, end) - bisect(bales, start - 1), file=out)

Problems