【刷题第六天】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
二、思路分析:
题目与以往接触略有区别,以往题目大多只有搜索索引情况,但本题目加入了如果搜索不到,则添加到对应位置。
虽然增加了一个额外条件,但第一想法还是二分查找,只不过在于如何修改条件,能满足额外情况。
二分查找变体一般都在与修改判断条件。我们考虑插入位置 pos,应该满足下列条件:
nums[pos−1]< target <=nums[pos]
nums[pos-1]< target <=nums[pos]
nums[pos−1]< target <=nums[pos]
nums 为排列数组,如果存在这个值,最终的结果也是返回 pos 位置,如果不存在则在 pos 位置插入值,因此本题目可以转化为 寻找第一个大于等于 target 的下标
通过上面的分析,我们已经成功的把该问题转化为了二分查找问题,下面开始套模板: 即通过使用二分法逼近查找第一个大于等于 target 的下标。
如果 target 大于数组中的所有元素,就会插入在第 n 个位置。因此下面代码中 res 初始值赋值为 n,可以避免这种情况的特殊判断。
三、AC 代码:
复制代码
四、总结:
好久没有做二分查找的问题了,第一瞬间竟然没有转化好,转化成功后,可以很清楚的看到这就是个二分问题。加油!!!
评论