Binary Search

Binary search is an efficient searching algorithm that works on sorted data. It repeatedly divides the search space in half by comparing the target value to the middle element. By eliminating half of the remaining elements on each step, binary search achieves much faster lookup times than linear search.

Because of this requirement, binary search is commonly paired with sorting algorithms in real-world systems.

Example Walk-through

Consider this sorted array:

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

We want to find the value 23.

Step 1 - Check the middle element

Middle index: (0 + 9) / 2 = 4 Middle value: 16

23 > 16 → discard the left half.

Search range becomes:

[23, 38, 56, 72, 91]

Step 2 - Check the new middle

Middle value: 38

23 < 38 → discard the right half.

Search range becomes:

[23]

Step 3 - Match found

Middle value: 23 → target found.

Binary search completes in only a few steps by systematically reducing the search space.

Rust Implementation

This implementation performs an iterative binary search and returns the index of the target value if found.

pub fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;

        match arr[mid].cmp(&target) {
            std::cmp::Ordering::Equal => return Some(mid),
            std::cmp::Ordering::Less => left = mid + 1,
            std::cmp::Ordering::Greater => right = mid,
        }
    }

    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_finds_existing_element() {
        let input = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
        assert_eq!(binary_search(&input, 23), Some(5));
    }

    #[test]
    fn it_returns_none_for_missing_element() {
        let input = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
        assert_eq!(binary_search(&input, 7), None);
    }
}

Example Usage

fn main() {
    let values = vec![1, 3, 5, 7, 9, 11, 13];
    let target = 7;

    match binary_search(&values, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found", target),
    }
}

Time and Space Complexity

Binary search reduces the search space by half on each iteration.

Space Complexity

When to Use Binary Search

Binary search is ideal when:

• The data is sorted
• Fast lookups are required
• Random access to elements is available (e.g., arrays or slices)

It is not suitable when:

• The data is unsorted
• Insertions and deletions happen frequently
• Data structures do not support indexed access

Playground Links

Rust - Binary Search