LeetCode热题100_搜索插入位置（63_35_简单_C++）(二分查找)(”＞＞“与“/”)

LeetCode 热题 100_搜索插入位置（63_35） 题目描述：输入输出样例：题解：解题思路：思路一（二分查找）： 代码实现代码实现（思路一（二分查找））：以思路一为例进行调试部分代码解读

题目描述：

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

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

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

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

”>>“ 与 “/”

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

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

LeetCode 热题 100_搜索插入位置（63_35)原题链接 欢迎大家和我沟通交流(✿◠‿◠)