Binary search: bounds and searching for answers
Turn every binary search into “find the first true”, handle duplicates with lower and upper bound, and binary-search over possible answers instead of array positions.
The key idea: find the first true
a[i] >= 12?”. In a sorted array the answers always look like F F F F T T T: all false, then all true. Binary search can find the boundary, the first true, in O(log n), whatever the question is, as long as the answers have that shape.
Lower bound and upper bound
Lower bound of x: the first index with a[i] >= x. If x is present, this is its first occurrence.Upper bound of x: the first index with a[i] > x. This is just after the last occurrence.The number of copies of x is upper − lower. Values in a range[from, to]areUpperBound(to) − LowerBound(from).
// Half-open range [lo, hi): hi starts at Length, "past the end" is a valid answerstatic int LowerBound(int[] a, int x){ int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] >= x) hi = mid; // mid could be the first true: keep it else lo = mid + 1; // mid is false: the answer is after it } return lo; // lo == hi: the first true (or Length)} static int UpperBound(int[] a, int x){ int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] > x) hi = mid; else lo = mid + 1; } return lo;} int[] a = { 2, 4, 4, 4, 7, 7, 9, 12, 12, 12, 12, 15 };Console.WriteLine($"12 starts at {LowerBound(a, 12)}, count {UpperBound(a, 12) - LowerBound(a, 12)}");Console.WriteLine($"values in [4, 9]: {UpperBound(a, 9) - LowerBound(a, 4)}");12 starts at 7, count 4 values in [4, 9]: 6
Binary search on the answer
[7, 2, 5, 10, 8] hours and must be split, in order, among 2 drafters. What is the smallest possible maximum workload for one drafter? A limit of 10 does not work (it needs 4 drafters); 32 (everything to one person) always works. Somewhere in between is the smallest limit that works.
// Can the tasks be split, in order, into at most k groups, each with total <= limit?static bool CanSplit(int[] tasks, int k, int limit){ int groups = 1, current = 0; foreach (int t in tasks) { if (current + t > limit) { groups++; current = 0; } // start a new drafter current += t; } return groups <= k;} static int MinLargestWorkload(int[] tasks, int k){ int lo = tasks.Max(), hi = tasks.Sum(); // the answer is somewhere in here while (lo < hi) { int mid = lo + (hi - lo) / 2; if (CanSplit(tasks, k, mid)) hi = mid; // works: try smaller else lo = mid + 1; // too small: go bigger } return lo;} Console.WriteLine(MinLargestWorkload([7, 2, 5, 10, 8], 2));18
Last true: the integer square root
lo up on true. Round mid up so the range always shrinks:
// Largest x with x * x <= nstatic long ISqrt(long n){ long lo = 0, hi = n; while (lo < hi) { long mid = lo + (hi - lo + 1) / 2; // round up, or lo = mid could loop forever if (mid <= n / mid) lo = mid; // mid*mid <= n, written to avoid overflow else hi = mid - 1; } return lo;} Console.WriteLine(ISqrt(26));Console.WriteLine(ISqrt(1_000_000));5 1000
target, or (-1, -1) if it is missing. For { 5, 7, 7, 8, 8, 10 }: 8 → (3, 4), 6 → (−1, −1). Use LowerBound and UpperBound.
Show a hint
a[first] != target, it is missing. Otherwise last = UpperBound(target) − 1.
Show the solution
static (int First, int Last) SearchRange(int[] a, int target){ int first = LowerBound(a, target); if (first == a.Length || a[first] != target) return (-1, -1); return (first, UpperBound(a, target) - 1);} int[] a = { 5, 7, 7, 8, 8, 10 };Console.WriteLine(SearchRange(a, 8));Console.WriteLine(SearchRange(a, 6));(3, 4) (-1, -1)
Remember
Every binary search can be phrased as “find the first true” on F…F T…T answers. Lower bound = first a[i] >= x, upper bound = firsta[i] > x; their difference counts copies.Binary search on the answer: if “does X work?” is monotonic, search the range of X. Use one template consistently to avoid infinite loops and off-by-one errors.