二分查找 Binary Search

问题描述

这个题目是最基础的二分查找法.

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

// Binary Search
// 直接法, 找到元素后就直接返回.
pub fn search1(nums: Vec<i32>, target: i32) -> i32 {
    // 先处理极端情况.
    if nums.is_empty() || nums[0] > target || nums[nums.len() - 1] < target {
        return -1;
    }

    // 左闭右闭区间
    let mut low = 0;
    let mut high = nums.len() - 1;

    // 退出循环的条件是 left > right.
    while low <= high {
        // 防止整数平均值溢出.
        let middle = low + (high - low) / 2;
        match nums[middle].cmp(&target) {
            Ordering::Less => low = middle + 1,
            Ordering::Equal => return middle as i32,
            Ordering::Greater => {
                if middle < 1 {
                    return -1;
                } else {
                    high = middle - 1;
                }
            }
        }
    }
    -1
}
}

二分查找法之排除法

这种是二分查找法的变体, 与上面的方法不同在于边界值的范围, 这里使用的是 左闭右开区间.

#![allow(unused)]
fn main() {
// Binary Search
// 排除法
pub fn search2(nums: Vec<i32>, target: i32) -> i32 {
    if nums.is_empty() || nums[0] > target || nums[nums.len() - 1] < target {
        return -1;
    }

    // 左闭右开区间
    let mut left = 0;
    let mut right = nums.len();

    // 终止循环的条件是 left == right
    while left < right {
        // 中间节点的计算不一样.
        let mid = left + (right - left) / 2;
        // 排除 [left, mid] 区间, 在 [mid + 1, right) 区间内查找
        if nums[mid] < target {
            left = mid + 1;
        } else {
            // 排除 [mid, right] 区间, 在 [left, mid) 区间内查找
            right = mid;
        }
    }

    // 检查剩余空间内的元素, nums[left] == nums[right] == target
    if left < nums.len() && nums[left] == target {
        left as i32
    } else {
        -1
    }
}
}

标准库中自带的二分查找法实现

标准库的 slice::binary_search() 及其变体函数, 就实现了经典的二分查找法, 性能比较好:

#![allow(unused)]
fn main() {
// Binary Search
// 使用标准库中自带的方法
pub fn search3(nums: Vec<i32>, target: i32) -> i32 {
    match nums.binary_search(&target) {
        Ok(index) => index as i32,
        Err(_) => -1,
    }
}
}