搜索插入位置
...大约 2 分钟
35.搜索插入位置
题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
解题思路
本题的思路与二分查找的思路十分相似，甚至可以说代码也十分相似，我们可以回忆一下二分查找的思路，本题也就迎刃而解了。
代码如下
func searchInsert(nums []int, target int) int {
left := 0
n := len(nums)
right := n - 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 left //最终left 指向的是比目标大一位的数 right指向的是比目标值小一位的数
}
复杂度分析
时间复杂度：
O(logn），其中n为数组的长度。二分查找所需的时间复杂度为O(logn)。空间复杂度：
O(1)。我们只需要常数空间存放若干变量。
总结
本题直接引用了二分查找的代码，稍作了修改，插入的位置 pos，它成立的条件为：
nums[pos−1]<target≤nums[pos]
其中 nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 target的下标」。
