Binary Search

Binary search is an algorithm that helps you find an item in a sorted list much faster than if you were to search for it one by one. It works by repeatedly dividing the search interval in half until the target value is found.

To understand how binary search works, let’s use the example of finding the number 7 in the sorted list 2, 4, 5, 7, 8, 9, 10, 13, 14, 15

First, we start by looking at the middle element of the list, which is 8. Since 7 is smaller than 8, we can eliminate the right half of the list and focus only on the left half: 2, 4, 5, 7.

Next, we repeat the same process, looking at the middle element of this new list, which is 4. Since 7 is greater than 4, we can eliminate the left half of the list and focus only on the right half: 5, 7.

We repeat this process again, looking at the middle element of this new list, which is 5. Since 7 is greater than 5, we can eliminate the left half of the list and focus only on the right half: 7.

Finally, we have narrowed the search down to a single element, which is 7. We have found our target!

Here’s an illustration step by step:

and a Rust implementation:

pub fn binary_search(items: &[u8], item: u8) -> Option<u8> {
    let mut lower_bound = 0;
    let mut upper_bound = items.len() - 1;

    while lower_bound <= upper_bound {
        let middle = (lower_bound + upper_bound) / 2;
        let guess = items[middle];

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

        if guess > item {
            upper_bound = middle - 1;
        } else {
            lower_bound = middle + 1;
        }
    }

    None
}

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

    #[test]
    fn valid_cases() {
        let items = [2, 4, 5, 7, 8, 9, 10, 13, 14, 15];
        let item = 7;

        let result = binary_search(&items, item);
        assert_eq!(result, Some(item));
    }

    #[test]
    fn invalid_cases() {
        let items = [1, 3, 5, 7, 9];
        let non_existing_item = 4;

        let result = binary_search(&items, non_existing_item);
        assert_eq!(result, None);
    }
}

You can derive the following formula to clearly understand the let middle = (lower_bound + upper_bound) / 2;

Let x = middle; y = lower_bound and z = upper_bound

\begin{aligned} x &= y + z \left(\frac{z - y}{2}\right) \\ 2x &= 2 \left(y + z \left(\frac{z - y}{2}\right)\right) \\ 2x &= 2y + 2 \left(\frac{z - y}{2}\right) \\ 2x &= 2y + \frac{2z - 2y}{2} \\ 2x &= 2y + \frac{1}{2}z - \frac{1}{2}y \\ 2x &= y + z \\ \frac{2x}{2} &= \frac{y + z}{2} \\ \frac{2}{2}x &= \frac{y + z}{2} \\ x &= \frac{y + z}{2} \end{aligned}

In summary, binary search is an efficient algorithm for finding a target value in a sorted list by repeatedly dividing the search interval in half. By eliminating half of the list in each iteration, the algorithm can quickly find the target value in logarithmic time.

References