Binary Search And Feasibility Optimization

What's being tested

This tests binary search correctness: loop invariants, boundary updates, duplicate handling, and safe midpoint calculation. It also tests binary-search-on-answer, where you minimize a feasible value k using a monotonic predicate, plus basic subset-sum dynamic programming for combinatorial feasibility.

Patterns & templates

• Classic binary search — `binary_search`(nums, target) in O(log n) time, O(1) space; use mid = lo + (hi - lo) // 2.

• First occurrence / lower bound — find smallest index with nums[i] >= target; use half-open interval [lo, hi) to reduce off-by-one errors.

• Last occurrence / upper bound — find largest index with nums[i] <= target; implement via `upper_bound`(target) - 1 and validate bounds afterward.

• Recursive binary search — same invariant as iterative version, but O(log n) stack space; always define base case before computing mid.

• Binary search on answer — search k over [1, max(workloads)]; predicate can_finish(k) must be monotonic and usually costs O(n).

• Minimum feasible rate — if hours(k) = sum(ceil(x / k)), then larger k never increases hours; total complexity O(n log M).

• Subset sum DP — `can_sum`(nums, target) via boolean array dp[target+1], update descending; O(n * target) time, O(target) space.

Common pitfalls

Pitfall: Updating lo = mid or hi = mid without progress can infinite-loop; use lo = mid + 1 when discarding mid.

Pitfall: Returning mid immediately for duplicates fails first/last occurrence variants; keep searching after recording a candidate.

Pitfall: Treating subset sum as greedy is wrong; use DP unless constraints clearly allow meet-in-the-middle or bitset optimization.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.