0035. 搜索插入位置 Search Insert Position

问题描述

这个使用二分查找法.

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

// Binary search
pub fn search_insert1(nums: Vec<i32>, target: i32) -> i32 {
    // 先检查边界情况.
    if nums.is_empty() || target <= nums[0] {
        return 0;
    }
    let last = nums.len() - 1;
    if target > nums[last] {
        return nums.len() as i32;
    }
    if target == nums[last] {
        return last as i32;
    }

    // 左闭右闭区间
    let mut left: usize = 1;
    let mut right: usize = last;

    // 终止循环的条件是 nums[left] > nums[right].
    // 此时 left 所在位置就是 target 插入到数组中的位置.
    while left <= right {
        let middle = left + (right - left) / 2;
        match nums[middle].cmp(&target) {
            Ordering::Less => left = middle + 1,
            Ordering::Equal => return middle as i32,
            // 这里 middle - 1 并不会出现整数 underflow
            Ordering::Greater => right = middle - 1,
        }
    }

    left as i32
}
}

另外, 标准库中的 slice::binary_search() 函数, 也可以查找目标元素 target 的期望位置:

#![allow(unused)]
fn main() {
// 使用 slice::binary_search()
pub fn search_insert2(nums: Vec<i32>, target: i32) -> i32 {
    match nums.binary_search(&target) {
        Ok(index) => index as i32,
        Err(index) => index as i32,
    }
}
}