Binary Search

Binary search locates a target value or boundary in a sorted sequence (or over a monotonic decision space) in $O(\log n)$ time by halving the search interval on every comparison. In Rust, slice::partition_point is the universal, duplicate-safe primitive for lower_bound and upper_bound queries on slices.

Sorted Slice with Duplicates:
  Index:    0    1    2    3    4    5    6
  Values: [ 10 | 20 | 40 | 40 | 40 | 70 | 90 ]
                      ^              ^
                      |              +-- `upper_bound(40)` = index 5 (`partition_point(|&x| x <= 40)`)
                      +----------------- `lower_bound(40)` = index 2 (`partition_point(|&x| x < 40)`)
                      Count of `40`s = 5 - 2 = 3!

binary_search vs partition_point (lower_bound / upper_bound)

While slice.binary_search(&target) returns Ok(idx) when target is found or Err(insert_idx) when missing, if the slice contains multiple duplicate copies of target, binary_search may return the index of any of the duplicates!

Whenever you need the first index $\ge \text{target}$ (C++ std::lower_bound) or the first index $> \text{target}$ (C++ std::upper_bound), always use slice.partition_point(predicate):

• slice.partition_point(|x| pred(x)) assumes the slice is partitioned such that pred(x) is true for a prefix 0..idx and false for the suffix idx..len, and returns the exact boundary index idx (0..=slice.len()).

pub fn lower_bound<T: Ord>(slice: &[T], target: &T) -> usize {
    slice.partition_point(|x| x < target)
}

pub fn upper_bound<T: Ord>(slice: &[T], target: &T) -> usize {
    slice.partition_point(|x| x <= target)
}

pub fn count_occurrences<T: Ord>(slice: &[T], target: &T) -> usize {
    upper_bound(slice, target) - lower_bound(slice, target)
}

fn main() {
    let arr = [10, 20, 40, 40, 40, 70, 90];

    assert_eq!(lower_bound(&arr, &40), 2);
    assert_eq!(upper_bound(&arr, &40), 5);
    assert_eq!(count_occurrences(&arr, &40), 3);

    // Missing element `55`: both lower_bound and upper_bound return insertion index 5:
    assert_eq!(lower_bound(&arr, &55), 5);
    assert_eq!(count_occurrences(&arr, &55), 0);

    println!(
        "Range of 40 in arr: {}..{} (count={})",
        lower_bound(&arr, &40),
        upper_bound(&arr, &40),
        count_occurrences(&arr, &40)
    );
}

Range of 40 in arr: 2..5 (count=3)

Binary Search on the Answer (Parametric Search)

Many optimization problems ask for the minimum capacity C (or maximum threshold) that satisfies a monotonic feasibility check can_complete(C)—where can_complete is false for small C and true for all C >= optimal.

Use the overflow-safe midpoint formula let mid = low + (high - low) / 2; over the half-open or closed search range:

/// Finds the minimum ship capacity needed to transport `weights` in at most `max_days` days.
pub fn min_ship_capacity(weights: &[u64], max_days: u64) -> u64 {
    let mut low: u64 = *weights.iter().max().expect("non-empty weights");
    let mut high: u64 = weights.iter().sum();

    let is_feasible = |cap: u64| -> bool {
        let mut days = 1u64;
        let mut current_load = 0u64;
        for &w in weights {
            if current_load + w > cap {
                days += 1;
                current_load = w;
            } else {
                current_load += w;
            }
        }
        days <= max_days
    };

    while low < high {
        let mid = low + (high - low) / 2;
        if is_feasible(mid) {
            high = mid; // `mid` works; try smaller capacities in `[low..=mid]`
        } else {
            low = mid + 1; // `mid` is too small; search `[mid + 1..=high]`
        }
    }

    low
}

fn main() {
    let packages = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let min_cap = min_ship_capacity(&packages, 5);
    assert_eq!(min_cap, 15);
    println!("Minimum ship capacity for 5 days: {min_cap}");
}

Minimum ship capacity for 5 days: 15