Leetcode刷题详解——搜索插入位置

1. 题目链接：35. 搜索插入位置

2. 题目描述：

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

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

3. 算法思路（二分查找）

• 设插入坐标为index，根据插入位置的特点可以知道：

  • [left,index-1]内所有元素均是小于target的
  • [index,right]内所有元素均是大于等于target的

• 设left为左边界，right为有边界，根据mid位置的信息，决定下一轮的区间范围：

  • 当nums[mid]>=target时，说明mid落在了[index，right]区间上，mid包括mid本身，可能是最终结果，所以我们接下来查找的区间在[left,mid]上。因此更新right到mid位置，继续查找
  • 当nums[mid]<target时，说明mid落在了[left,index-1]区间上，mid右边但不包括mid本身，可能是最终结果，所以我们接下来查找的区间在[mid+1,right]上。因此更新left到mid+1的位置，继续查找

• 直到我们的查找结果的长度变为1，也就是left==right的时候，left或者right所在的位置就是我们要找的结果

4. C++算法代码

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