Chapter 82

Binary Search on Arrays

Binary search finds an element in a sorted array in O(log N) — halving the search space each time. It's the most fundamental divide-and-conquer algorithm.

Classic Binary Search

C++ — binary search

int binary_search(vector& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // avoid overflow
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// C++ also has std::binary_search (bool), lower_bound, upper_bound

Rust — binary search

fn binary_search(arr: &[i32], target: i32) -> Result {
    arr.binary_search(&target)
    // Returns Ok(index) or Err(insertion_point)
}

💡 mid = lo + (hi - lo) / 2

Avoid (lo + hi) / 2 — it can overflow for large ints. lo + (hi - lo) / 2 is safe.

Key Takeaways

→Binary search: O(log N) on sorted arrays.
→Use lo + (hi-lo)/2 to avoid overflow.
→Built-in: std::binary_search/lower_bound (C++), .binary_search() (Rust).