搜索插入位置（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小的下一位，刚好是需要插入的位置。