What is binary search?

What is binary search?

binary search is an algorithm to efficiently find a specific target value within a sorted array or list.
For instance, If I decide to number from 0 to 100, you have to guess the number that I decided as few times as possible.
I will say you "This number is low" or "This number is high", when you guess the number and it is't correct.
If you use simple search, you have to guess max 99times.
It's not good.

How to specific target value more efficiently?

There is a better way to specific target more efficiently.
This is starting at 50.
If I decided 99, 50 is too small.
Therefore, You can exclude from 0 to 50.
Next, You guess 75, the middle between 51 and 100 is 75, 75 is too small.
Therefore, You can also exclude from 50 to 75.
When you do this some times, you will specify the number I decided!
This is a binary search.

How many times can the target number be found if a binary search is used?

For a list of elements, in the worst case, a binary search requires log2n steps.

Logarithm

Logarithm is x when x = loga b
We use it when we think What power of 'a' will result in 'b'?
Therefore, log10 100 means "What power of 10 will result in 100?".
The answer is 2 because of 10 * 10 = 100.

How to write in Rust

We can implement this algorithm in Rust like this.

fn binary_search(list: &[i32], item: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = list.len() - 1;

    while low <= high {
        let mid = (low + high) / 2;
        let guess = list[mid];

        if guess == item {
            return Some(mid);
        }

        if guess > item {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    None
}

fn main() {
    let my_list = vec![1, 3, 5, 7, 9];
    println!("{:?}", binary_search(&my_list, 3)); // Output: Some(1)
    println!("{:?}", binary_search(&my_list, -1)); // Output: None
}

Summary

Binary search is a one of basis of algorithms.
Let's use it well!