Binary Search on a Sorted Array

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

Example - Counting Haybales

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.

Without Built-in Functions

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

With Built-in Functions

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