LeetCode 0035.搜索插入位置

搜索插入位置

题目描述

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

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

示例 1:

1
2


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

示例2：

1
2


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

示例3：

1
2


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

示例 4:

1
2


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

示例 5:

1
2


输入: 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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