一、搜索插入位置
题目解析
这道题,给定一个数组
nums和一个目标值target,让我们在数组nums中找到目标值;如果目标值存在就返回它的下标,如果不存在就返回数target被顺序插入的位置下标。
算法思路
这道题,我们可以使用暴力查找,时间复杂度是 O(n)。
从左到右遍历数组,找到值大于等于
target的起始位置(如果target不存在,那要找的就是target顺序插入的位置)
题目要求我们要使用时间复杂度为 O(log n) 的算法来解决,暴力解法的时间复杂度为 O(n)(暴力解法虽然可以通过这道题)
思考以下:数组 nums 是有序的,且我们要找的是 >=target 的起始位置,那也就是大于等于 target 区间的左端点;
我们再随机挑选一个位置 i,区间 [0,i-1] 中的数都是小于 i 位置的数;区间 [i+1 , n] 中的数都是大于 i 位置的数的。
那我们就可以使用二分查找
首先定义
left和right指向数组的起始位置和结束位置。取mid = left + (right - left)/2比较mid位置的值和target如果nums[mid] > target,就去左边区间查找;right = mid - 1。如果nums[mid] < target,就去右边区间查找;left = mid + 1。如果nums[mid] == target,就查找到了target,就返回当前位置下标即可。这里因为我们要查找的是>=target区间的左端点,所以在遍历结束后,l指向的就是target顺序排序的插入位置。
代码实现
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - ;
(l <= r) {
mid = (l + r) / ;
(nums[mid] < target) l = mid + ;
(nums[mid] > target) r = mid - ;
mid;
}
l;
}
};


