Step 2 of 7

Linear and binary search

Linear search looks at the items one by one: v.contains(&x), v.iter().position(|&y| y == x). It's O(n) and works on any data.

Binary search needs sorted data and is O(log n): look at the middle item; if it's too small, the answer can only be in the right half, otherwise in the left half. Each step halves what's left, so a million items take at most 20 steps.

Slices have it built in:

• v.binary_search(&x) returns Ok(index) if x is there, or Err(index) with the position where x would have to be inserted to keep v sorted.
• v.partition_point(|&y| y < x) returns the first index where the condition becomes false. The condition must be true for a first part of the slice and false for the rest, which is exactly what a sorted slice gives you. It's the tool for "how many items are below x?" and "where does the run of x start?".
• binary_search_by_key and binary_search_by search on a field or with your own comparison.

fn main() {
    let scores = [12, 25, 25, 25, 40, 58, 71];
    println!("{:?}", scores.binary_search(&40));
    println!("{:?}", scores.binary_search(&30));

    let first_25 = scores.partition_point(|&s| s < 25);
    let after_25 = scores.partition_point(|&s| s <= 25);
    println!("25 is at {first_25}..{after_25}, {} times", after_25 - first_25);

    let passed = scores.len() - scores.partition_point(|&s| s < 50);
    println!("{passed} scores are 50 or more");

    let mut sorted = vec![10, 20, 30];
    let pos = sorted.binary_search(&25).unwrap_or_else(|insert_at| insert_at);
    sorted.insert(pos, 25);
    println!("{sorted:?}");
}

Ok(4)
Err(4)
25 is at 1..4, 3 times
2 scores are 50 or more
[10, 20, 25, 30]

With duplicates, binary_search may return any of the matching positions; use partition_point when you need the first or last one.

Writing it yourself

Interviewers love asking for binary search by hand because it's easy to get subtly wrong. The safest shape is a half-open range lo..hi: the answer, if it exists, is at an index with lo <= index < hi. Start with lo = 0, hi = len, and loop while lo < hi:

• let mid = lo + (hi - lo) / 2; (never past hi - 1, and it can't overflow)
• middle too small: the answer is right of it, lo = mid + 1
• middle too big: the answer is left of it, hi = mid

Common mistakes

• Binary search on unsorted data. No error, just wrong answers. Sort first, or keep the data sorted.
• Mixing inclusive and half-open bounds. hi = len - 1 with while lo < hi stops without ever checking the last remaining candidate; hi = mid - 1 with usize panics with attempt to subtract with overflow when mid is 0. Pick half-open and use hi = mid.
• (lo + hi) / 2 can overflow when lo and hi are big values of a small type, like the u32 capacities in the last challenge of this step; lo + (hi - lo) / 2 can't, so make it a habit.
• A partition_point condition that isn't "true then false". For a sorted slice, |&y| y < x is fine; |&y| y == x is not.

Your task

Write fn find(sorted: &[i32], target: i32) -> Option<usize> by hand with a half-open range (no binary_search or partition_point). The values are sorted and all different; return the index of target, or None. The tests look up 200,000 values in a slice of 200,000, so a linear scan is too slow.

Challenge 2

Reaction times (in milliseconds) from a game are kept sorted. The analytics page asks many questions like "how many players reacted between 180 and 250 ms (inclusive)?".

Write fn count_in_range(sorted: &[u32], low: u32, high: u32) -> usize with two calls to partition_point: one finds where values >= low start, the other where values > high start. Return 0 when low > high. The tests ask 100,000 questions about 200,000 values.

Challenge 3

Binary search on the answer. A warehouse ships packages along a conveyor in a fixed order. Each day the truck is loaded with packages in order for as long as the load stays within its capacity (a load exactly equal to the capacity is fine); packages are never split. Write fn min_capacity(packages: &[u32], days: u32) -> u32: the smallest truck capacity that ships everything within days days (days is at least 1). Return 0 for no packages.

The trick: if capacity c is enough, every bigger capacity is too. So "is c enough?" is false, false, ..., true, true over the capacities, and you can binary search for the first true between max(package) (the smallest that can carry everything) and sum(packages) (one day). Write a helper that counts the days a capacity needs. The tests have 100,000 packages, so trying capacities one by one is too slow.

Previous: Big-O: counting the work Next: Sorting and custom orderings