2020/2/15

题目描述

• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

• 你可以假设数组中无重复元素。

示例

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

相关标签

数组
二分查找

解题思路

• 如果该题目暴力解决的话需要 O(n) 的时间复杂度，但是如果二分的话则可以降低到 O(logn) 的时间复杂度，空间复杂度为O(1)。
• 整体思路和普通的二分查找几乎没有区别，先设定左侧下标 left 和右侧下标 right，再计算中间下标 mid
  每次根据 nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则 left = mid + 1，nums[mid] > target 则 right = mid - 1左移
• 查找结束如果没有相等值则返回 left，该值为插入位置

源代码

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let (mut st, mut ed, mut ans) = (0, nums.len() - 1, 0);
        while st <= ed {
            let mid = st + (ed - st) / 2;
            if target == nums[mid] {
                return mid as i32;
            } else if target < nums[mid]{
                if mid == 0 {
                    return 0;
                }
                ed = mid - 1;
            } else{
                st = mid + 1;
            }
        }
        st as i32
    }
}

• 执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
• 内存消耗 : 2.1 MB, 在所有 Rust 提交中击败了76.47%的用户

总结

• 值得注意的是，在Rust中，自动的类型判断和检查会将数组的index认为是usize类型，注意当index=0时，如- 果再减1，可能会造成index溢出的现象，如要单独进行判断来排除这类情况。另外，index与别的整型变量交互式也需要额外的类型转换(as 关键字)。
• 可以通过模式匹配的方法一次性初始化多个同类型或者不同类型变量。
• 也可以通过Vec标准库中的binary_search配合闭包来实现。

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        nums.binary_search(&target).unwrap_or_else(|x| x) as i32
    }
}