每日leetcode

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

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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

提示:

• 1 <= nums.length <= 104

• -104 <= nums[i] <= 104

• nums 为 无重复元素 的 升序 排列数组

• -104 <= target <= 104

思路

1. 我们的目标是找到target的位置在什么位置，如果不在，要让定位到的位置是比他大的最小的那个元素的位置或者直接就是末尾。
2. 那么还是定义左右边界，因为可能会在末尾，所以左边界是0，右边界直接就是nums.size()。
3. 然后只要left<right，就不断取中间，如果小于target，那么就变成n+1，如果大于或者等于就让右边界等于n。
4. 最后退出循环后直接返回右边界即可。

代码实现

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size(), n;while(left < right) {n = (left+right)/2;if(nums[n] < target) left = n + 1;else right = n;}return right;}
};

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(1)。

官方题解

• 我的代码短，好读，用我的。