太原富库网站建设网页设计代码免费

35. 搜索插入位置 - 力扣（LeetCode）

解法：二分查找

思路：题目是有序的，时间复杂度O(logN),二分没跑了，题目说如果找不到target，返回它应该被插入位置的下标，所以可以分析一下示例2：

可以把数组分为两部分，当找到>=target区间的左端点时，它的下标正好是要被输出的下标，所以

1.数组有二段性，可以用二分

2.用求区间左端点的方法解决这道题。不了解的看这个在做题中学习（49）：排序数组中查找元素的第一个和最后一个位置-CSDN博客

细节

因为有示例3这种，数组元素都比target小的情况，所以此时单独判断，如果数组最后一个元素<target，返回num.size()即可。

class Solution 
{
public:int searchInsert(vector<int>& nums, int target) {int left = 0,right = nums.size()-1;if(nums[nums.size()-1] < target)return nums.size();int mid = 0;while(left<right){//1.找区间左端点mid = left + (right - left) /2;if(nums[mid] < target)left = mid + 1;else right = mid;}//走到这里,返回左端点return left;}
};