2023-02-20.md

题目

35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

思路

1. [l,r]为答案的范围，因为target可能大于nums[n-1]，所以l=0,r=n
2. m = l+(r-l)/2避免overflow
3. nums[m] < target，答案至少为m+1
4. nums[m] > target，答案至多为m
5. 考虑剩下3个、2个、1个元素的情况，当剩下1个元素时，如果nums[m] > target则陷入死循环，需要跳出循环，所以while的条件为l<r

代码

// runtime 70.90% memory 64.76%
var searchInsert = function(nums, target) {
  let l = 0
  let r = nums.length
  while (l < r) {
    const m = Math.floor(l + (r - l) / 2)
    if (nums[m] == target) return m
    else if (nums[m] < target) l = m + 1
    else r = m
  }
  return l
}