LeetCode 面试经典 150_二分查找_搜索插入位置（111_35_C++_简单）

题目描述：

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

请必须使用时间复杂度为 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 <= 10⁴
-10⁴<= nums[i] <= 10⁴
nums 为 无重复元素 的 升序 排列数组
-10⁴<= target <= 10⁴

题解：

解题思路：

思路一（二分查找）：

1、搜索插入位置，如果数组中之前存在与插入元素相同大小的元素，则之前元素的位置便是插入位置。如果之前不存在相同大小的元素，则插入到对应大小的位置。
2、具体思路如下：
我们每次查找取中间的元素与插入元素进行比对：
① 若中间元素等于插入元素则返回中间元素的下标。
② 若中间元素小于插入元素则插入元素的位置肯定在中间元素的右侧。
③ 若中间元素大于插入元素则插入元素的位置肯定在中间元素的左侧。
④ 依次进行查找，直到查找到对应位置。(二分查找结束没找到元素时，**左下标(left)**正好是插入的位置)

3、复杂度分析：
① 时间复杂度：O(logn)，其中n为数组的长度。（每次将搜索范围缩小一半）
② 空间复杂度：O(1)。使用常数空间存放若干变量。

代码实现

代码实现（思路一（二分查找））：

classSolution{public:intsearchInsert(vector<int>&nums,inttarget){// 初始化左右指针：left指向数组的开始，right指向数组的末尾intleft=0,right=nums.size()-1,mid;// 使用二分查找算法，当 left <= right 时继续查找while(left<=right){// 计算中间元素的索引，避免整数溢出mid=((right-left)>>1)+left;// 如果中间元素大于目标值，说明目标值在左半部分if(nums[mid]>target){right=mid-1;// 调整右指针，缩小搜索范围到左半部分}// 如果中间元素小于目标值，说明目标值在右半部分elseif(nums[mid]<target){left=mid+1;// 调整左指针，缩小搜索范围到右半部分}// 如果中间元素等于目标值，直接返回中间元素的索引else{returnmid;}}// 如果没有找到目标值，返回应该插入的位置，也就是 left 指针的位置returnleft;}};

以思路一为例进行调试

#include<iostream>#include<vector>usingnamespacestd;classSolution{public:intsearchInsert(vector<int>&nums,inttarget){// 初始化左右指针：left指向数组的开始，right指向数组的末尾intleft=0,right=nums.size()-1,mid;// 使用二分查找算法，当 left <= right 时继续查找while(left<=right){// 计算中间元素的索引，避免整数溢出mid=((right-left)>>1)+left;// 如果中间元素大于目标值，说明目标值在左半部分if(nums[mid]>target){right=mid-1;// 调整右指针，缩小搜索范围到左半部分}// 如果中间元素小于目标值，说明目标值在右半部分elseif(nums[mid]<target){left=mid+1;// 调整左指针，缩小搜索范围到右半部分}// 如果中间元素等于目标值，直接返回中间元素的索引else{returnmid;}}// 如果没有找到目标值，返回应该插入的位置，也就是 left 指针的位置returnleft;}};intmain(){// 定义一个整数向量 nums，初始化为 {1, 3, 5, 6}vector<int>nums={1,3,5,6};// 定义目标值 target，设定为 5inttarget=5;// 创建一个 Solution 类的对象 sSolution s;// 调用 searchInsert 方法，传入 nums 和 target，返回插入位置并输出// 该函数返回 target 的插入位置，如果已存在则返回目标值的索引cout<<s.searchInsert(nums,target);return0;}

部分代码解读

”>>“ 与 “/” 对比

(right-left)>>1(right-left)/2

效率上，(right - left) >> 1 比 (right - left) / 2更高效，尤其在低级语言或不进行优化的情况下。
在现代编译器和硬件上，差异可能非常小，因为编译器可能会将除法优化为类似位移的操作，特别是对整数类型。

LeetCode 面试经典 150_二分查找_搜索插入位置（111_35)原题链接
欢迎大家和我沟通交流(✿◠‿◠)