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

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

思路

  1. 在常规二分查找的基础上，处理未命中 target 的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var searchInsert = function (nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] > target) {
      right = mid - 1
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      return mid
    }
  }
  if (nums[left] >= target) {
    return left
  }
  return left + 1
}