搜索插入位置（35）
35. 搜索插入位置 - 力扣（LeetCode）
相关算法：二分查找最左侧和最右侧target的index-CSDN博客
class Solution {
public:
int searchInsert(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size() - 1;
int ans = nums.size();
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) {
right = mid - 1;
ans = mid;
}else {
left = mid + 1;
}
}
return ans;
}
};总结：
计算时间复杂度O(N)，空间复杂度O(1)。二分查找最左侧和最右侧target的index-CSDN博客 搜索最左侧的index，因为搜索最左侧的index，实际上是从右往左逼近。如果存在target，返回target的index，如果不存在target，这个时候ans记录的是比target小的下一位，刚好是需要插入的位置。