35. 搜索插入位置

[buuing]

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

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

示例 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-insert-position 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 暴力解题

const searchInsert = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i
  }
  return nums.length
}

• 二分法查找-递归

const searchInsert = (nums, target) => {
  const find = (start, end) => {
    const index = (start + end) / 2 >> 0
    const num = nums[index]
    if (start > end) return start
    if (num > target) {
      return find(start, index - 1)
    } else if (num < target) {
      return find(index + 1, end)
    } else {
      return index
    }
  }
  return find(0, nums.length - 1)
}

• 二分法查找-迭代 (效率最高)

const searchInsert = (nums, target) => {
  let start = 0, end = nums.length - 1
  while (start < end) {
    let i = (start + end) / 2 >> 0
    if (nums[i] === target) return i
    if (nums[i] > target) {
      end = i - 1
    } else {
      start = i + 1
    }
  }
  return nums[start] >= target ? start : start + 1
}