Binary search in Rust

Halve the range each step, with the index arithmetic the borrow checker is happy about.

fn binary_search(items: &[i32], target: i32) -> Option<usize> {
    let (mut lo, mut hi) = (0, items.len());
    while lo < hi {
        let mid = (lo + hi) / 2;
        if items[mid] == target {
            return Some(mid);
        }
        if items[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    None
}

Keywords and builtins used here

• None
• Option
• Some
• binary_search
• else
• fn
• i32
• if
• let
• mut
• return
• usize
• while

The run, in numbers

Lines

15

Characters to type

260

Tokens

96

Three-star pace

90 tpm

At the three-star pace of 90 tokens a minute, this run takes about 64 seconds.

Type this snippet

Step 4 of 8 in Collections, step 33 of 39 in Language basics.

← Previous Next →

Binary search in other languages

• C
• Go
• JavaScript
• Python
• R
• TypeScript