Search Space Reduction Patterns - Learning Module

Loading content...

0/279

Maintaining Invariants During Search

The Hidden Guardrails of Correct Algorithms

In the previous page, we learned that search space reduction derives its power from eliminating impossible regions. But this power comes with a critical risk: if we eliminate incorrectly—removing a region that actually contains our target—the algorithm produces wrong results.

How do we guarantee that our eliminations are always sound? How do we know that our shrinking search space always contains the target (if it exists)?

The answer lies in one of the most important concepts in algorithm design: loop invariants. An invariant is a condition that remains true throughout the execution of an algorithm, providing a mathematical guarantee that our logic never goes astray.

What You Will Learn

By the end of this page, you will understand: (1) what loop invariants are and why they matter, (2) how to formulate precise invariants for search algorithms, (3) how invariants get established, maintained, and leveraged, and (4) practical techniques for writing bug-free search code by thinking in invariants.

What Is a Loop Invariant?

Definition: A loop invariant is a logical condition that:

Is true before the loop begins (initialization)
Remains true after each iteration (maintenance)
Provides useful information when the loop terminates (termination)

Think of an invariant as a contract the algorithm maintains with itself. At any point during execution, if someone pauses the algorithm and checks, the invariant should hold.

Why "Invariant"?

The term comes from Latin invariare (to not change). Despite the loop variable changing, the index advancing, and the search space shrinking—the invariant remains constant, unchanged, invariant.

The Three Stages of Invariant Reasoning:

Invariant Lifecycle

•Initialization — Prove the invariant holds before the first iteration. This is usually straightforward but essential—if the invariant isn't true at the start, everything falls apart.
•Maintenance — Prove that if the invariant holds before an iteration, it still holds after the iteration. This is the heart of the proof—showing each step preserves the guarantee.
•Termination — Show that when the loop ends, the invariant (combined with the exit condition) gives us our desired result.

Mathematical Induction Connection

If you've studied mathematical induction, invariant reasoning will feel familiar. The initialization is the base case, and maintenance is the inductive step. We're essentially doing induction on loop iterations.

The Binary Search Invariant

Let's make invariants concrete by examining binary search. Every correct binary search implementation maintains a specific invariant:

Binary Search Invariant: If the target exists in the array, it exists within the range [left, right].

Equivalently stated:

All elements at indices < left are confirmed less than target
All elements at indices > right are confirmed greater than target
We have not yet determined whether target exists in [left, right]

Let's trace how this invariant is established, maintained, and used:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
function binarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    // ═══════════════════════════════════════════════════════════════
    // INITIALIZATION: Invariant established
    // ═══════════════════════════════════════════════════════════════
    // 
    // Invariant: If target exists in arr, then target ∈ arr[left..right]
    // 
    // Proof of initialization:
    //   - left = 0, right = arr.length - 1
    //   - [left, right] = [0, n-1] = entire array
    //   - If target exists anywhere in arr, it exists in arr[0..n-1] ✓
    //   - No elements have been examined yet, so no false eliminations
    // ═══════════════════════════════════════════════════════════════
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (arr[mid] === target) {
            // Target found! Invariant says target is in [left, right],
            // and we just confirmed target = arr[mid] where left ≤ mid ≤ right ✓
            return mid;
        }
        
        if (arr[mid] < target) {
            // ═══════════════════════════════════════════════════════
            // MAINTENANCE CASE 1: arr[mid] < target
            // ═══════════════════════════════════════════════════════
            // 
            // We know: arr[mid] < target
            // Array is sorted: arr[0..mid] ≤ arr[mid] < target
            // Therefore: arr[0..mid] < target (target cannot be in [0..mid])
            // 
            // By setting left = mid + 1:
            //   - We eliminate [0..mid] from consideration
            //   - New range [mid+1, right] still contains target (if it exists)
            //   - Invariant preserved ✓
            // ═══════════════════════════════════════════════════════
            left = mid + 1;
        } else {
            // ═══════════════════════════════════════════════════════
            // MAINTENANCE CASE 2: arr[mid] > target
            // ═══════════════════════════════════════════════════════
            // 
            // We know: arr[mid] > target
            // Array is sorted: target < arr[mid] ≤ arr[mid..n-1]
            // Therefore: target < arr[mid..n-1] (target cannot be in [mid..n-1])
            // 
            // By setting right = mid - 1:
            //   - We eliminate [mid..n-1] from consideration
            //   - New range [left, mid-1] still contains target (if it exists)
            //   - Invariant preserved ✓
            // ═══════════════════════════════════════════════════════
            right = mid - 1;
        }
    }
    
    // ═══════════════════════════════════════════════════════════════
    // TERMINATION: Loop exit with left > right
    // ═══════════════════════════════════════════════════════════════
    //
    // Exit condition: left > right
    // Invariant still holds: if target exists, it's in [left, right]
    // But [left, right] is now empty (left > right means no valid indices)
    // 
    // Since our invariant says target (if exists) is in an empty set,
    // and nothing can exist in an empty set → target does not exist
    // ═══════════════════════════════════════════════════════════════
    
    return -1;  // Target not found
}

Why This Works:

The invariant creates a logical fence around our search. At every moment, we know exactly what has been proven impossible and what remains possible. The beauty is that when the possible region becomes empty, we've exhaustively proven impossibility through deduction rather than examination.

Strategies for Formulating Invariants

Formulating the right invariant is an art. A good invariant is:

True — It actually holds throughout execution
Useful — Combined with termination conditions, it proves correctness
Checkable — We can verify it during debugging or testing

Here are proven strategies for discovering strong invariants:

Invariant Discovery Techniques

•State the Goal — What are you trying to prove when the loop ends? Work backwards from there. If you need 'target found' or 'target proven absent', your invariant should be 'target is in [left, right] if it exists anywhere'.
•Describe Partitions — Consider what each region of the array represents. 'Everything left of left is less than target' is a partition description that becomes an invariant.
•Track What's Been Eliminated — Frame the invariant in terms of what has been proven impossible. 'Indices 0 to left-1 have been eliminated' is sometimes clearer than 'target is in [left, right]'.
•Consider the Bounds — For index-based searches, invariants often describe the relationship between left/right bounds and the target's possible location.
•Trace Small Examples — Run through a small array manually, writing down what's true after each iteration. The pattern often reveals the invariant.

Example: First Occurrence Binary Search

When finding the first occurrence of a target in a sorted array with duplicates, the standard invariant changes slightly. We need to track that we're finding the leftmost occurrence:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function findFirstOccurrence(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    
    // INVARIANT: If target appears anywhere in arr, 
    //            its FIRST occurrence is in [left, right] OR already in 'result'
    //            
    // Subtle difference: When we find target, we don't stop—we continue
    // searching left to find an earlier occurrence
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (arr[mid] === target) {
            // Found an occurrence! But is it the first?
            // Record it as a candidate, then search LEFT for an earlier one
            result = mid;
            right = mid - 1;  // Eliminate [mid, right] — look for earlier occurrence
            
            // MAINTENANCE: If a first occurrence exists before mid, it's in [left, mid-1]
            //              If mid WAS the first occurrence, we've stored it in 'result'
            //              Either way, the answer is in [left, right] ∪ {result} ✓
            
        } else if (arr[mid] < target) {
            left = mid + 1;  // Eliminate left half — first occurrence must be later
        } else {
            right = mid - 1;  // Eliminate right half — first occurrence must be earlier
        }
    }
    
    // TERMINATION: [left, right] is empty
    // If result != -1, we found at least one occurrence and result holds the leftmost
    // If result == -1, target doesn't exist
    
    return result;
}

Invariant Complexity Matches Problem Complexity

Notice how the 'first occurrence' variant needed a more complex invariant that tracks both the remaining search space AND the best result found so far. Harder problems require more sophisticated invariants. This is a feature, not a bug—the invariant captures the additional complexity.

The Closed vs. Open Interval Debate

One of the most common sources of confusion and bugs in binary search is the choice between closed intervals [left, right] and half-open intervals [left, right). Each leads to different loop conditions, update rules, and invariants.

Let's examine both approaches carefully:

Closed vs. Half-Open Interval Binary Search
Aspect	Closed [left, right]	Half-Open [left, right)
Initialization	left = 0, right = n - 1	left = 0, right = n
Invariant	target in [left, right] inclusive	target in [left, right) exclusive of right
Loop Condition	while (left <= right)	while (left < right)
Search Space Empty	When left > right	When left == right
Left Update	left = mid + 1	left = mid + 1
Right Update	right = mid - 1	right = mid
Common In	Textbooks, LeetCode	STL algorithms, lower_bound/upper_bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// STYLE 1: Closed interval [left, right]
function binarySearchClosed(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;  // right is VALID index
    
    // Invariant: target in arr[left..right] (both inclusive)
    
    while (left <= right) {  // Space is non-empty when left <= right
        const mid = left + Math.floor((right - left) / 2);
        
        if (arr[mid] === target) return mid;
        
        if (arr[mid] < target) {
            left = mid + 1;    // [left, mid] eliminated, [mid+1, right] remains
        } else {
            right = mid - 1;   // [mid, right] eliminated, [left, mid-1] remains
        }
    }
    return -1;  // left > right means empty space
}
 
// STYLE 2: Half-open interval [left, right)
function binarySearchHalfOpen(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length;  // right is PAST the last valid index
    
    // Invariant: target in arr[left..right) (left inclusive, right exclusive)
    
    while (left < right) {  // Space is non-empty when left < right
        const mid = left + Math.floor((right - left) / 2);
        
        if (arr[mid] === target) return mid;
        
        if (arr[mid] < target) {
            left = mid + 1;    // [left, mid] eliminated, [mid+1, right) remains
        } else {
            right = mid;       // [mid, right) eliminated, [left, mid) remains
            // Note: mid excluded because right is exclusive
        }
    }
    return -1;  // left == right means empty space
}

Which Should You Choose?

Both are correct when implemented consistently. The key is internal consistency—mixing conventions causes bugs. Recommendations:

Master one style thoroughly — Most programmers find closed intervals more intuitive for basic binary search.
Use half-open for bounds problems — When finding insertion positions, lower_bound, or upper_bound, half-open intervals map more naturally to the semantics.
Document your choice — If you're writing library code or working on a team, make the convention explicit.
Be extra careful when adapting — Many bugs occur when copying code that uses a different convention than you expect.

The +1/-1 Asymmetry

In closed intervals, both updates use '+1' and '-1'. In half-open, only the left update uses '+1' (right update is just 'mid'). This asymmetry trips up many programmers. The reason: in half-open, 'right' already excludes index 'right', so setting 'right = mid' correctly excludes 'mid' from consideration.

Debugging with Invariants

Invariants aren't just theoretical tools—they're practical debugging weapons. When a binary search fails, the invariant points directly to the bug.

Debugging Strategy: Invariant Checking

Add explicit invariant checks to your code during development. If a bug exists, the check will catch it early:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function binarySearchDebug(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    // INVARIANT CHECK FUNCTION
    const checkInvariant = () => {
        // If target exists, verify it's in [left, right]
        const targetIdx = arr.indexOf(target);
        if (targetIdx !== -1) {
            if (targetIdx < left || targetIdx > right) {
                console.error(`INVARIANT VIOLATED! Target at ${targetIdx}, but bounds are [${left}, ${right}]`);
                console.error(`We incorrectly eliminated the target!`);
                throw new Error("Invariant violation");
            }
        }
    };
    
    // Check initialization
    checkInvariant();
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        console.log(`Searching [${left}, ${right}], mid=${mid}, arr[mid]=${arr[mid]}`);
        
        if (arr[mid] === target) return mid;
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        
        // Check maintenance after each iteration
        checkInvariant();
    }
    
    console.log(`Search exhausted. Target not in array.`);
    return -1;
}
 
// Run with: binarySearchDebug([1, 3, 5, 7, 9, 11], 7)
// Output shows each step and verifies invariant holds

Common Bugs Detectable via Invariant Checking:

Bugs That Violate Invariants

•Off-by-one in elimination — Using mid instead of mid + 1 or mid - 1 can include or exclude indexes incorrectly. Invariant check catches when target leaves bounds.
•Wrong comparison operator — Using < instead of ≤ in loop condition. Fails when search space is single element.
•Flipped inequality — Checking arr[mid] > target when you meant <. Eliminates the wrong half.
•Integer overflow — Computing mid as (left + right) / 2 can overflow. Invariant won't catch this directly, but wrong mid leads to wrong elimination.
•Wrong array indexing — Accessing arr[mid] when mid is out of bounds. Caught before invariant check as array access fails.

Remove Checks in Production

Invariant checks are O(n) in this example (using indexOf), making them unsuitable for production. Use them during development and testing, then remove for production code. Some languages support debug-only assertions that are automatically stripped.

Invariants in Complex Search Scenarios

As search problems become more complex, invariants become more nuanced. Let's explore invariants for several challenging scenarios:

Scenario 1: Search in Rotated Sorted Array

In a rotated sorted array like [4, 5, 6, 7, 0, 1, 2], the invariant must account for the rotation point:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function searchRotated(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    // INVARIANT: If target exists in arr, it's in arr[left..right]
    // 
    // KEY INSIGHT: At any point, at least ONE of [left, mid] or [mid, right]
    // is sorted. We determine which, then check if target falls in that range.
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (arr[mid] === target) return mid;
        
        // Determine which half is sorted
        if (arr[left] <= arr[mid]) {
            // LEFT HALF [left, mid] IS SORTED
            // Invariant extension: arr[left] ≤ arr[left+1] ≤ ... ≤ arr[mid]
            
            if (arr[left] <= target && target < arr[mid]) {
                // Target falls within sorted left half
                right = mid - 1;  // Eliminate unsorted right half
            } else {
                // Target NOT in sorted left half → must be in right half
                left = mid + 1;   // Eliminate sorted left half
            }
            // Invariant maintained: target (if exists) is still in [left, right]
            
        } else {
            // RIGHT HALF [mid, right] IS SORTED
            // Invariant extension: arr[mid] ≤ arr[mid+1] ≤ ... ≤ arr[right]
            
            if (arr[mid] < target && target <= arr[right]) {
                // Target falls within sorted right half
                left = mid + 1;   // Eliminate unsorted left half
            } else {
                // Target NOT in sorted right half → must be in left half
                right = mid - 1;  // Eliminate sorted right half
            }
            // Invariant maintained: target (if exists) is still in [left, right]
        }
    }
    
    return -1;  // Empty search space, target not found
}

Scenario 2: Binary Search on Answer Space

When binary searching for an optimal value (not an array index), the invariant describes the feasibility of the answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Ship capacity problem: Find minimum capacity to ship packages in 'days' days
 * Packages must be shipped in order, each day's load ≤ capacity
 */
function minShipCapacity(weights: number[], days: number): number {
    // Answer space: [max(weights), sum(weights)]
    // - Minimum possible: must handle largest single package
    // - Maximum possible: ship everything in one day
    
    let left = Math.max(...weights);
    let right = weights.reduce((a, b) => a + b, 0);
    
    // INVARIANT: 
    //   - All capacities in [left, right] MAY be feasible
    //   - All capacities < left are PROVEN infeasible
    //   - Optimal answer is in [left, right]
    
    const canShipInDays = (capacity: number): boolean => {
        let daysNeeded = 1;
        let currentLoad = 0;
        
        for (const w of weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;
                currentLoad = w;
            } else {
                currentLoad += w;
            }
        }
        return daysNeeded <= days;
    };
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (canShipInDays(mid)) {
            // Capacity 'mid' works! But maybe something smaller works too.
            // MAINTAIN: Optimal is in [left, mid] (mid is valid, might be optimal)
            right = mid;
        } else {
            // Capacity 'mid' is too small.
            // MAINTAIN: Optimal is in [mid+1, right] (mid is proven infeasible)
            left = mid + 1;
        }
    }
    
    // TERMINATION: left == right
    // By invariant: optimal is in [left, right] = [left, left] = exactly 'left'
    return left;
}

Monotonicity Is Key

Binary search on answer space works because feasibility is monotonic: if capacity C works, then capacity C+1 also works. This monotonicity creates the structure needed for elimination. If feasibility weren't monotonic, binary search wouldn't apply.

Developing the Invariant Mindset

Thinking in invariants is a skill that develops with practice. Here's how to cultivate this mindset:

Before Writing Code:

•State what you want to prove when the algorithm terminates
•Work backwards: what condition, maintained throughout, would give you that conclusion?
•Write the invariant in precise language
•Sketch how initialization establishes it
•Consider each branch: does it preserve the invariant?

While Writing Code:

•Comment the invariant at the top of the loop
•For each update (left = mid + 1, etc.), write why it preserves invariance
•At loop exit, note how invariant + exit condition proves correctness

When Debugging:

•State your invariant explicitly
•Trace through the failing case, checking invariant after each step
•The first step where the invariant breaks reveals the bug
•Fix the step that violates invariance

Without Invariant Thinking

•"Let me try mid - 1... no, mid + 1"
•"Why does this infinite loop?"
•"It works on some inputs but not others"
•"I'll just add special cases until it works"
•Trial and error debugging

With Invariant Thinking

•"The invariant requires mid + 1 here"
•"Loop doesn't shrink space—invariant violation"
•"Let me check which step breaks the invariant"
•"The invariant handles all cases correctly"
•Systematic, principled debugging

Summary: Invariants as Correctness Guardrails

Loop invariants transform search algorithms from fragile hacks into provably correct procedures. Let's consolidate the key insights:

Key Takeaways

•Invariants are contracts — Conditions that hold true before, during, and after every loop iteration.
•Three stages: Initialize, Maintain, Terminate — Establish the invariant, preserve it per iteration, leverage it at exit.
•Invariants guide elimination — They guarantee that eliminated regions truly cannot contain the target.
•Interval conventions matter — Closed [L, R] and half-open [L, R) require different update rules. Be consistent.
•Invariant checks enable debugging — Runtime verification pinpoints exactly where logic fails.
•Complex problems need complex invariants — Rotated arrays, answer-space search, and other variants require nuanced invariant formulation.

Looking Ahead:

With elimination principles and invariant maintenance in hand, we're ready to examine the most elegant form of search space reduction: half-interval elimination. This is where the logarithmic magic happens—cutting the search space precisely in half with each comparison. We'll see why 'half' is special and how to achieve it consistently.

Page Complete

You now understand how invariants provide the logical foundation for correct search algorithms. An invariant is your algorithm's promise to itself—a condition that, if maintained, guarantees correctness. Master this concept, and binary search bugs become a thing of the past.