力扣35-搜索插入位置[二分法]

原题

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

请必须使用时间复杂度为 O(log n) 的算法。


示例 1:

> 输入: nums = [1,3,5,6], target = 5
> 输出: 2

示例 2:

> 输入: nums = [1,3,5,6], target = 2
> 输出: 1

示例 3:

> 输入: nums = [1,3,5,6], target = 7
> 输出: 4

提示

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

解题思路

已知

• 有序数组
• 目标值 target

求

• 若有 target，返回索引
• 若无 target 返回顺序插入位置（right 位置）

空状态处理

• 空数组，返回 0

解题过程

1. 初始化左右指针：left = 0, right = len(nums) - 1
   • （假设区间为 [l, r] 左右均闭合区间，结束外层循环时: l > r，当 target 比 l 小的时候，l 指向数组头；当 target < r 时，l 指向数组尾）
   • （假设区间为 [l, r) 左闭右开区间，结束外层循环时: l == r，直接返回 r 或者 l 都行 ）
2. 空数组，返回 0
3. 二分查找 target
   • 找到匹配的 target，返回 target 索引
   • 找不到匹配的 target，返回 right 指针位置

复杂度

代码

[l,r]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  // [l, r]
  const n = nums.length
  let l = 0
  let r = n - 1
  // l <= r 条件，循环结束的时候 r > l,此时 r 为左边界，适合处理插入尾部的操作和空数组的情况
  // l < r 条件，循环结束的时候 r == l,此时直接返回即可
  while (l <= r) {
    mid = (l + r) >>> 1
    if (target === nums[mid]) {
      return mid
    } else if (target > nums[mid]) {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }
  return r + 1
}

[l,r)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  // [l, r]
  const n = nums.length
  let l = 0
  let r = n
  // l <= r 条件，循环结束的时候 r > l,此时 r 为左边界，适合处理插入尾部的操作和空数组的情况
  // l < r 条件，循环结束的时候 r == l,此时直接返回即可
  while (l < r) {
    mid = (l + r) >>> 1
    if (target === nums[mid]) {
      return mid
    } else if (target > nums[mid]) {
      l = mid + 1
    } else {
      r = mid
    }
  }
  return r
  // return l 都是可以的
}