搜索插入位置

Tips

题目类型: 二分查找

题目

给定一个排序数组和一个目标值, 在数组中找到目标值, 并返回其索引. 如果目标值不存在于数组中, 返回它将会被按顺序插入的位置. 你可以假设数组中无重复元素.

提示:

• 1 <= nums.length <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• nums 为无重复元素的升序排列数组
• -10⁴ <= target <= 10⁴

示例

输入: nums = [1, 2, 3, 4], target = 2
输出: 1

输入: nums = [1, 3, 5, 6], target = 4
输出: 2
解释: 目标值 4 不存在, 且它应该插在索引为 2 的位置

题解

二分查找的基本框架. 如果 nums[mid] < target, 那 target 至少在 mid 的右边; 如果 nums[mid] > target, 那 target 至多在 mid 的左边. 嗯, 夹一下.

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0,
    right = nums.length - 1
  while (left <= right) {
    const mid = ((left + right) / 2) | 0

    if (nums[mid] === target) {
      return mid
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return left
}

Rust

pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
    let (mut left, mut right) = (0, nums.len() - 1);

    while left <= right {
        let mid = (right + left) / 2;

        if nums[mid] == target {
            return mid as i32;
        } else if nums[mid] < target {
            left = mid + 1;
        } else {
            // 注意 Rust 索引不能溢出, 否则报错
            if mid == 0 {
                return mid as i32;
            }
            right = mid - 1;
        }
    }

    left as i32
}

Rust - 自带 binary_search 方法

标准库中的二分法完美符合这道题的需要:

binary_search 的返回值类型为 Result<T,E> 类型

• 查找到, 会返回其索引, 类型对应 Ok(usize)
• 未查到, 则会返回当该序列按顺序排列时, 应被插入的索引, 类型对应 Err(usize)

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

复杂度分析

时间复杂度: O(logn)

空间复杂度: O(1)