二分查找

二分查找适用于已经排好序的数组，时间复杂度为 O(logn)

fn main() {
    let data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];

    let target = 10;
    let is_found = binary_search(&data, target);
    // 10 is in data: true
    println!("{target} is in data: {is_found}");

    let target = 20;
    let is_found = binary_search(&data, target);
    // 20 is in data: false
    println!("{target} is in data: {is_found}");

    let target = 10;
    let is_found = binary_search_recursive(&data, target);
    // recursive: 10 is in data: true
    println!("recursive: {target} is in data: {is_found}");

    let target = 20;
    let is_found = binary_search_recursive(&data, target);
    // recursive: 20 is in data: false
    println!("recursive: {target} is in data: {is_found}");
}

// 二分查找
fn binary_search(nums: &[i32], num: i32) -> bool {
    let mut low = 0;
    let mut height = nums.len() - 1;
    let mut found = false;

    while low <= height && !found {
        // 这个等于  mid = height / 2
        let mid = low + ((height - low) >> 1);

        if num == nums[mid] {
            found = true;
        } else if num < nums[mid] {
            // num < 中间值，省略后半部分
            height = mid - 1;
        } else {
            // num >= 中间值，省略前半部分
            low = mid + 1;
        }
    }

    found
}

// 递归二分查找版本
fn binary_search_recursive(nums: &[i32], num: i32) -> bool {
    if nums.len() == 0 {
        return false;
    }

    let mid = nums.len() >> 1;

    if num == nums[mid] {
        return true;
    } else if num < nums[mid] {
        // Rust 的 .. 运算符，不包括区间的右端点
        return binary_search_recursive(&nums[..mid], num);
    } else {
        return binary_search_recursive(&nums[mid + 1..], num);
    }
}

优化版二分查找