LeetCode 0035.搜索插入位置【Go】

搜索插入位置

leetcode35.搜索插入位置

题目描述

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

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

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例2：

输入: nums = [1,3,5,6], target = 2
输出: 1

示例3：

输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:

输入: nums = [1], target = 0
输出: 0

思路

题目要求

• 在有序数组中找到目标值，并返回索引
• 若未找到，则返回它将会被按顺序插入的位置

因为是在有序数组中查找元素，所以考虑使用二分查找法

若未找到目标元素，则有三种插入情况

• 目标值插入在数组所有元素之前
• 目标值插入在数组中
• 目标值插入在数组所有元素之后

注意

对未找到目标元素的三种插入情况分别进行分析

• 当目标值小于数组中最小值时，在最后一轮循环中，left = right = mid = 0，由于nums[mid] > target，所以判断target在左区间，执行right = mid - 1 = -1，即目标值要插入的位置为right + 1
• 当目标值小于数组中最大值时，最后一轮循环中，left = right = mid = len(nums)-1，由于nums[mid] < target，所以判断target在右区间，执行left = mid + 1 = len(nums)，即目标值要插入的位置为right + 1；
• 目标值插入在数组中时，在最后一轮循环中，target一定是插入数组中某个元素的位置x或其后面的位置x + 1。两种情况下：left = right = mid = x。若判断target > nums[mid]，则target在右区间，执行left = mid + 1，插入位置应为x + 1，即目标值要插入的位置为right + 1；若判断target < nums[mid]，则target在左区间，执行right = mid - 1，插入位置应为x，即目标值要插入的位置为right + 1。

由于数组在内存中是连续的内存空间，所以向数组中插入元素时，需要后移其后面的全部元素。当target比某个元素小，首先需要将该元素及其后面的元素全部后移，留出空位，然后将元素插入该位置。

综上，当使用二分法在有序数组中查找不到目标元素时，元素将会被按顺序插入的位置为right + 1。

代码

GO

func searchInsert(nums []int, target int) int {
  left := 0
  right := len(nums) - 1
  for left <= right {
    mid := left + (right - left ) / 2
    if nums[mid] == target {
      return mid
    } else if nums[mid] < target {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return right + 1
}

Link

GitHub