Image Source: Wikipedia

Input: A sorted list.

Algorithm:

1. Select the middle element.
2. If the desired element is less discard the right side or more discard the left side.
3. Repeat until found or no elements remain.

Average time complexity: $O(log(n))$

Rust implementation draft:

fn main()
{
    let numbers = [1, 2, 3, 4, 5, 6, 7];
    match find(&numbers, 3)
    {
        None => println!("3 not found"),
        Some(index) => println!("Found 3 at index {}.", index)
    }
}

fn find(numbers: &[i32], value: i32) -> Option<usize>
{
    if numbers.len() == 0
    {
        return None;
    }

    let middle_index = numbers.len() / 2;
    if value < numbers[middle_index]
    {
        find(&numbers[0..middle_index], value)
    }
    else if value > numbers[middle_index]
    {
        let start = middle_index + 1;
        match find(&numbers[start..numbers.len()], value)
        {
            None => None,
            Some(found_index) => Some(start + found_index)
        }
    }
    else
    {
        Some(middle_index)
    }
}