Binary Search Algorithm in Rust

1. Introduction

Binary Search is an efficient search algorithm that finds the position of a target value within a sorted array or collection. It compares the target value to the middle element and, based on this comparison, eliminates half of the search space. This process is repeated until the value is found or the interval has zero length.

2. Implementation Steps

1. Start with an interval covering the whole array.

2. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.

3. Repeatedly check until the value is found or the interval is empty.

3. Implementation in Rust Programming

fn binary_search<T: Ord>(arr: &[T], target: &T) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len();
    while low < high {
        let mid = (low + high) / 2;
        if &arr[mid] == target {
            return Some(mid);
        } else if &arr[mid] < target {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    None
}
fn main() {
    let numbers = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92];
    match binary_search(&numbers, &75) {
        Some(index) => println!("Found at index {}", index),
        None => println!("Not Found"),
    }
}

Output:

Found at index 7

Explanation:

1. The binary_search function is a generic function which works for any type T that implements the Ord trait, allowing for ordering comparisons.

2. We maintain two pointers, low and high, to represent the current search interval.

3. In each iteration, we compute the midpoint mid of the current interval.

4. If the mid element is equal to the target, we've found our item and return its index.

5. If the mid element is less than the target, it implies our target can only exist in the right (upper) half of the array. Thus, we set low to mid + 1.

6. If the mid element is greater than the target, it implies our target can only exist in the left (lower) half of the array. Thus, we set high to mid.

7. This process continues until our interval becomes empty or we find the target value.

8. In the main function, we demonstrate the usage of binary_search on a sorted array of numbers, searching for the number 75.