Binary search in Rust

You want the word "pelican" in a printed dictionary. You do not start at page one. You open it near the middle and see "mongoose". Pelican comes after that, so you ignore the entire first half. Now you open the middle of what is left, see "rabbit", and ignore the back half. A few flips later, you are on the right page.

That is binary search. Each look at the middle throws away half of what remains. It only works because a dictionary is sorted, so one look tells you which half to keep.

How fast is it? A dictionary of 1,000 pages takes about 10 looks. A million pages takes about 20. A billion takes about 30. Compare that with reading page by page. This is the speed of the idea, and it is why sorting (lesson 13) is worth doing first.

Reach for it when the data is sorted and you keep asking "where is this?". It also works in a quieter way, on a problem where the answer is a number and you can test whether a guess is too small or big enough. That second use is the one interviewers love.

Try it on eleven sorted numbers, hunting for 45. Keep track of the part still in play with two edges, lo on the left and hi on the right.

Look at the middle: 23. It is smaller than 45, so 45 cannot be in 23's half. Everything from 23 leftward is out. The left edge moves to just past the middle. Look at the middle of what is left: 56. Too big, so the right edge moves in. Look again: 45. Found, after three looks.

The pattern never changes. Look at the middle, compare, and move one edge. The picture shows the faded boxes that are ruled out.

Two details trip people up, so get them right now.

Is the right edge in or out? In this lesson hi is one past the end, just like Rust's ranges lo..hi. The search runs while lo < hi. Pick one convention and stick to it. Most binary search bugs are an edge that is off by one.

What if it is not there? Then the edges meet. The part in play shrinks to nothing, and lo ends up pointing at the gap where the item would go. That is a useful free gift, as you will see.

Remember: look at the middle, throw half away, and keep your edge rules the same on every step.

Here it is for a sorted slice of numbers.

/// Finds `target` in a sorted slice by halving the part still in play.
/// Returns its position, or `None` if it is not there.
pub fn find(sorted: &[i32], target: i32) -> Option<usize> {
    // The answer, if there is one, is always inside `lo..hi`.
    let (mut lo, mut hi) = (0, sorted.len());
    while lo < hi {
        // Not `(lo + hi) / 2`: adding two big numbers first can overflow.
        let mid = lo + (hi - lo) / 2;
        if sorted[mid] == target {
            return Some(mid);
        } else if sorted[mid] < target {
            lo = mid + 1; // everything up to `mid` is too small
        } else {
            hi = mid; // `mid` and everything after it is too big
        }
    }
    None
}

Go through it in order.

• The part in play is lo..hi. At the start that is the whole slice.
• mid is the middle of it. Writing lo + (hi - lo) / 2 instead of (lo + hi) / 2 is a habit worth having. With huge numbers, lo + hi can overflow before the division. It cannot overflow here, but the habit stops the bug in other languages.
• If the middle is the target, you are done. If it is too small, lo = mid + 1, because the middle itself has been checked and is wrong. If it is too big, hi = mid, because hi is one past the end and so is already excluded.
• When lo meets hi, nothing is left in play, and the answer is None.

The demo at the bottom also tries the first item, the last item, and a number that is missing. Edges are where the bugs live, so always test them.

There is a second way to use binary search, and it is the one interviewers love. When the answer is a number and you can test a guess, you can binary search over the numbers themselves. You need one thing: the test must go from "no, no, no" to "yes, yes, yes", and never flip back. Then the smallest "yes" can be found by halving.

/// The smallest number in `lo..hi` that passes `ok`, or `hi` if none do.
/// `ok` must go false, false, ..., true, true: once it is true, it stays true.
pub fn first_true(mut lo: u64, mut hi: u64, ok: impl Fn(u64) -> bool) -> u64 {
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if ok(mid) {
            hi = mid; // `mid` works, but something smaller might too
        } else {
            lo = mid + 1; // `mid` fails, and so does everything below it
        }
    }
    lo
}

first_true does not look at a slice. It looks at a range of numbers, and asks ok(mid). If mid passes, the answer is mid or something smaller, so hi = mid. If it fails, the answer is bigger, so lo = mid + 1. Here it finds the smallest whole number whose square is at least 1000, without trying all of them.

Remember: if "is this guess big enough?" has a clean yes or no, you can binary search the answer.

A slice has binary_search built in.

let marks = [10, 20, 30, 30, 30, 40];

// `binary_search` says Ok(position) if found, Err(where it would go) if not.
assert_eq!(marks.binary_search(&40), Ok(5));
assert_eq!(marks.binary_search(&25), Err(2));
assert_eq!(marks.binary_search(&5), Err(0));
assert_eq!(marks.binary_search(&99), Err(6));

// With repeats, it may return any one of them. `partition_point` is
// exact: it counts how many items at the front pass the test.
let first_30 = marks.partition_point(|&x| x < 30);
let after_30 = marks.partition_point(|&x| x <= 30);
println!("{} {}", first_30, after_30);
assert_eq!((first_30, after_30), (2, 5));
assert_eq!(after_30 - first_30, 3); // three 30s

binary_search gives back a Result. Ok(position) means found. Err(position) means not found, and the position is the gap where it would go to keep the slice sorted. When the slice has repeated values, it may return any of them. That is rarely what you want, so reach for partition_point instead.

partition_point(|x| test) assumes the slice starts with a run of items that pass the test and then switches to items that fail. It returns how many pass. In the example, x < 30 passes for 10 and 20, so the answer is 2, the position of the first 30. x <= 30 passes for five items, so the answer is 5, the position just after the last 30. Subtract the two and you have counted the 30s, with no loop.

The Err side is also how you insert into a sorted Vec and keep it sorted.

let mut marks = vec![10, 20, 40];
// The Err side is the gap to insert at, so the list stays sorted.
let at = marks.binary_search(&30).unwrap_or_else(|gap| gap);
marks.insert(at, 30);

println!("{:?}", marks);
assert_eq!(marks, [10, 20, 30, 40]);

If your data is a list of pairs sorted by their first part, binary_search_by_key does the same job on that part.

// Pairs sorted by their first part.
let roll = [(101, "Asha"), (104, "Ben"), (109, "Chen")];

let found = roll.binary_search_by_key(&104, |&(number, _)| number);
println!("{:?}", found);
assert_eq!(found, Ok(1));
assert_eq!(roll.binary_search_by_key(&105, |&(number, _)| number), Err(2));

All of these need the slice to be sorted in the order you search. On an unsorted slice they return nonsense, with no warning.

Remember: binary_search for "is it there?", partition_point for "where does it go, and how many?".

If you only search once, a plain scan can beat sorting first. Binary search pays off when you search the same data many times.

Each starter has a todo!(), a placeholder that panics if it runs. Replace it with your code.

pub fn search_insert(sorted: &[i32], target: i32) -> usize {
    todo!("the position of the target, or where it would go")
}

pub fn search_insert(sorted: &[i32], target: i32) -> usize {
    // Find the first spot whose value is not smaller than the target.
    let (mut lo, mut hi) = (0, sorted.len());
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if sorted[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    lo
}

pub fn mountain_peak(heights: &[i32]) -> usize {
    todo!("which way does the slope point at the middle?")
}

/// The list rises to one peak and then falls (it needs at least one height).
/// Returns the peak's position.
pub fn mountain_peak(heights: &[i32]) -> usize {
    let (mut lo, mut hi) = (0, heights.len() - 1);
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if heights[mid] < heights[mid + 1] {
            lo = mid + 1; // still climbing, so the peak is further right
        } else {
            hi = mid; // falling, so the peak is here or further left
        }
    }
    lo
}

pub fn min_speed(piles: &[u64], hours: u64) -> u64 {
    todo!("the smallest speed that still finishes in time")
}

pub fn min_speed(piles: &[u64], hours: u64) -> u64 {
    // At this speed, how many hours does it take? A pile of 7 at speed 3
    // takes 3 hours, because the last hour is only part used.
    let hours_needed = |speed: u64| piles.iter().map(|&p| p.div_ceil(speed)).sum::<u64>();

    // Speed 1 is the slowest that makes sense. The biggest pile is the
    // fastest anyone could need, since one hour handles one pile at most.
    let (mut lo, mut hi) = (1, piles.iter().copied().max().unwrap_or(1));
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if hours_needed(mid) <= hours {
            hi = mid; // fast enough, but maybe slower still works
        } else {
            lo = mid + 1;
        }
    }
    lo
}

Binary search is simple to explain and surprisingly easy to get wrong. Interviewers know that, and they watch for the details.

• Spot the signals. "Sorted", "find the first or last", "minimum that works", "maximum that still fits", and "in O(log n)" all point here. If a brute force would try every number in a range, ask whether the tries could be halved.
• Say the invariant. Before you code, say what is always true: "the answer is always inside lo..hi". Then check that every move keeps it true.
• Choose your edge rules once. Say whether hi is included or one past the end, and write every line to match. A mixed-up pair of rules is the most common bug.
• Test the edges. Try an empty slice, one item, the first item, the last item, and a missing item. Say you will do that, and then do it.
• Know the lookups. "Where would this go?" is the first position that is not smaller. "How many equal?" is two such positions subtracted. In Rust, that is partition_point.
• Use it when it is not obviously a search. Questions about "the smallest capacity", "the slowest speed" or "the largest size" are often a search on the answer. The test is a clean yes or no, and the cost is O(log range) tests.
• Sort cost matters. If the data is not sorted, sorting first costs O(n log n). For one lookup, a scan is faster. Mention that trade-off.

Made by VeraStack Labs