Binary search is an algorithm used to search a sorted array to find the position of a value.

It works by dividing the array in half until the value is found or the subdivision of the array is empty. The array is split by comparing the target value with the middle value of the array being searched.

It's important to note that for the algorithm to work as intended, the array must be sorted.

Solution

C Flavored

fn binary_search(haystack: Vec<i32>, needle: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = haystack.len() - 1;

    while low <= high {
        let mid = low + (high - low) / 2;

        if haystack[mid] == needle {
            return Some(mid);
        }

        if haystack[mid] < needle {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    None
}

Rust Flavored

use std::cmp::Ordering;

fn binary_search(haystack: Vec<i32>, needle: i32) -> Option<usize> {
    let mut low = 0;
    let mut mid = haystack.len() / 2;
    let mut high = haystack.len() - 1;

    while low <= high {
        match haystack[mid].cmp(&needle) {
            Ordering::Equal => return Some(mid),
            Ordering::Less => low = mid + 1,
            Ordering::Greater => high = mid - 1,
        }

        mid = low + (high - low) / 2;
    }

    return None;
}

Explanation

We initialize two variables, low and high to mark the lower and upper bound of the search space.

let mut low = 0;
let mut high = haystack.len() - 1;

While the range is not empty (low <= high), we calculate the middle point of the search space.

while low <= high {
    let mid = low + (high - low) / 2;
}

If the needle is in the middle, we return the index of the middle value mid.

if haystack[mid] == needle {
    return Some(mid);
}

Otherwise we check whether needle is greater or smaller than the value at mid, and shrink the search space accordingly.

• If the needle is greater than the middle value, we resize the search space by moving the lower bound to the start of the upper half (mid + 1).
• In the opposite case, we move the upper bound to the lower half (mid - 1).

if haystack[mid] < needle {
    // move the lower bound to the upper half
    low = mid + 1;
} else {
    // move the higher bound to the lower half
    high = mid - 1;
}

If the while loop ends (meaning we didn't find the needle in the haystack), return None.