Chapter 83

Home

Refactoring: Lower and Upper Bound

Writing binary search yourself is error-prone. C++ provides lower_bound (first ≥ val) and upper_bound (first > val). Rust's binary_search returns the insertion point. Using them correctly avoids off-by-one bugs.

Before: Hand-Rolled Binary Search

C++ — error-prone manual search

// Find first index where arr[i] >= target
// Easy to get lo/hi boundaries wrong
int lo = 0, hi = n-1, ans = n;
while (lo <= hi) {
    int mid = lo + (hi-lo)/2;
    if (arr[mid] >= target) { ans = mid; hi = mid-1; }
    else lo = mid+1;
}

After: Using Built-in Bounds

C++ — lower_bound / upper_bound

vector arr = {1, 3, 3, 5, 7, 9};

int idx = lower_bound(arr.begin(), arr.end(), 3) - arr.begin();
// ↑ index of first element ≥ 3 → 1

idx = upper_bound(arr.begin(), arr.end(), 3) - arr.begin();
// ↑ index of first element > 3 → 3

// Count occurrences of 3:
int count = upper_bound(arr.begin(), arr.end(), 3)
          - lower_bound(arr.begin(), arr.end(), 3);
// ↑ 2

// Requires sorted array — O(log N)

Rust — partition_point

let arr = vec![1, 3, 3, 5, 7, 9];

let idx = arr.partition_point(|x| *x < 3);
// ↑ first element ≥ 3 → 1

let idx = arr.partition_point(|x| *x <= 3);
// ↑ first element > 3 → 3

// Count occurrences:
let count = arr.partition_point(|x| *x <= 3)
           - arr.partition_point(|x| *x < 3);
// ↑ 2

Key Takeaways