每日一题---35. 搜索插入位置[力扣][Go]

// 遍历
func searchInsert(nums []int, target int) int {
  index := 0
  for i, num := range nums {
    index = i
    if target <= num {
      break
    }
    index++
  }
  return index
}

// 二分法
func searchInsert(nums []int, target int) int {
  n := len(nums)
  // 定义左右闭区间[l , r]
  l := 0
  r := n-1
  // 因为是闭区间所以 l = r 也有效
  for l <= r {
    // 控制范围
    mid := l + (r - l)/2
    if nums[mid] > target {
      // target 在左区间，所以[l, mid - 1]
      r = mid - 1
    } else if nums[mid] < target {
      // target 在右区间，所以[mid + 1, r]
      l = mid + 1
    } else {
      // 1. 目标值等于数组中某一个元素  return mid;
      return mid
    }
  }
  // 2.目标值在数组所有元素之前 3.目标值插入数组中 4.目标值在数组所有元素之后 return r + 1;
  return r + 1
}