Binary Search — Practice Problems

Thirteen problems that drill the binary-search pattern from Lesson 10 — the plain “find an element” variety, the rotated-array twists, and the powerful “binary search on the answer” family. Open a problem, try it yourself first, then read how to reach the solution. Each solution here was actually run and tested.

How to practise. The bugs in binary search are always the boundaries. Before you code, fix two things in your head: the invariant (is the answer always inside [lo, hi]?) and the exit condition (lo <= hi when you return from inside the loop; lo < hi when the answer is wherever the pointers meet). For the “search on the answer” ones, first write the ok(x) feasibility check, then binary-search the smallest x that passes.

Three of the solutions below use the standard library — add these imports at the top:

import bisect
import math
from collections import defaultdict