Binary search discards impossible regions
Start with a sorted random-access array or a monotone predicate. For lower bound, maintain a half-open candidate interval [low, high) and seek the first element at least the target. Each comparison removes a region that cannot contain that boundary. Consistent endpoint rules avoid infinite loops and duplicate-value bugs. A binary search over a linked list does not get the same cheap midpoint access.
Two pointers need a proof
On a sorted array, if left plus right is too small, decreasing right cannot increase the sum, so advancing left is safe. If the sum is too large, reduce right. Without sorted order this reasoning fails. Sorting first may be worthwhile, but it changes index positions and adds cost; preserve original indices if the required answer refers to the input ordering.
Sliding windows maintain a property
A window is a contiguous interval with incrementally maintained state. For unique characters, track counts or last-seen positions and move the left edge until the invariant holds. For a minimum length reaching a sum, the common shrink rule relies on nonnegative values; arbitrary negatives can invalidate it. Before coding, articulate what extension and contraction do to validity and what information the window retains.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
static int lowerBound(int[] a, int target) {
int low = 0, high = a.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (a[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}Walkthrough
For [2, 4, 4, 9] and target 4, low/high start at 0/4. Mid 2 contains 4, so high becomes 2. Mid 1 contains 4, so high becomes 1. Mid 0 contains 2, so low becomes 1. The interval is empty and index 1 is the first valid boundary. Returning a.length means no element meets the condition.
Practice it yourself
Test lowerBound with an empty array, all duplicates, a target smaller than every value, and a target greater than every value.
Check your reasoning
The empty array returns 0. For [4,4,4] targeting 4, return 0; targeting 5, return 3. For a smaller target return 0. The return is an insertion boundary, not necessarily a matching index, so verify equality separately if membership is required.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.