题目描述

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

请必须使用时间复杂度为 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

提示:

1 <= nums.length <= 10410^{4}104
−104-10^{4}−104 <= nums[i] <= 10410^{4}104
nums 为无重复元素的升序排列数组
−104-10^{4}−104 <= target <= 10410^{4}104

题目分析

看完题目，第一反应就是用二分查找法解题。

但是又有点纠结，因为题目还有个条件是：如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

这个要怎么搞才好呢？

好好想了一下，二分法是可以解题的，因为如果目标值不存在数组中，那么他应该被插入的位置就是找到比他小的数字的下标+1。

我又参考了一下大神的解题思路：

不断用二分法逼近查找第一个大于等于 target 的下标 。

思路讲解

1. 我们获得数组的长度，使用二分法进行查找
2. ans 初值设置为数组长度可以省略边界条件的判断（大神不愧是大神，开始我就没考虑到~）

AC代码

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

运行结果

总结

复杂度分析

时间复杂度：O(logn)，其中 n 为数组的长度。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。