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

  1. 输入: [1,3,5,6], 5
  2. 输出: 2

示例 2:

  1. 输入: [1,3,5,6], 2
  2. 输出: 1

示例 3:

  1. 输入: [1,3,5,6], 7
  2. 输出: 4

示例 4:

  1. 输入: [1,3,5,6], 0
  2. 输出: 0

解法一：二分查找

这个问题可以转化为一个经典的 求大于等于定值的第一个位置
需要注意的是：

  • 这里不需要对于最后结果的越界处理，因为如果越界表示我们需要把 target 插入到最后。 ```go // 转变为求第一个大于等于的 key func searchInsert(nums []int, target int) int { n := len(nums) lo, hi := 0, n-1 for lo <= hi {
    1.   mid := lo + (hi-lo)>>1
    2.   if nums[mid] >= target {
    3.       hi = mid - 1
    4.   } else {
    5.       lo = mid + 1
    6.   }
    } return lo }
  1. 另一种二分形式：同样不需要检测越界，所以最后的还是直接返回 lo 即可。
  2. ```go
  3. func searchInsert(nums []int, target int) int {
  4.     n := len(nums)
  5.     lo, hi := 0, n-1
  6.     for lo <= hi {
  7.         mid := lo + (hi-lo)>>1
  8.         if nums[mid] >= target {
  9.             if mid == 0 || nums[mid-1] < target {
  10.                 return mid
  11.             }
  12.             hi = mid - 1
  13.         } else {
  14.             lo = mid + 1
  15.         }
  16.     }
  17.     return lo
  18. }