【练习】【二分】力扣热题10035.搜索插入位置]

题目 搜索插入位置

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

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

来源：力扣热题100 35. 搜索插入位置

---

---

纯代码 class Solution { public: int searchInsert(vector<int>& nums, int target) { int n = nums.size(), l = 0, r = n - 1; if (nums[n - 1] < target) return n; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } return r ; } }; 题解（加注释） #include <vector> class Solution { public: // 该函数用于在一个升序排序的整数数组 nums 中查找目标值 target 应该插入的位置 // 如果 target 已经存在于数组中，返回其索引；如果不存在，返回它将会被插入的位置索引 int searchInsert(std::vector<int>& nums, int target) { // 获取数组 nums 的长度 int n = nums.size(); // 初始化二分查找的左边界，从数组的第一个元素开始 int l = 0; // 初始化二分查找的右边界，到数组的最后一个元素 int r = n - 1; // 先进行一个边界检查，如果数组的最后一个元素都小于目标值 target // 说明 target 应该插入到数组的末尾，直接返回数组的长度 n if (nums[n - 1] < target) return n; // 开始二分查找过程，只要左边界 l 小于右边界 r，就继续循环 while (l < r) { // 计算中间位置的索引，使用位运算 l + r >> 1 等同于 (l + r) / 2 // 这样做是为了避免在 l 和 r 都很大时，(l + r) 可能会导致整数溢出 int mid = l + r >> 1; // 如果中间位置的元素 nums[mid] 大于或等于目标值 target // 说明目标值可能在左半部分或者就是中间位置，更新右边界为 mid if (nums[mid] >= target) { r = mid; } // 否则，即中间位置的元素 nums[mid] 小于目标值 target // 说明目标值在右半部分，更新左边界为 mid + 1 else { l = mid + 1; } } // 当循环结束时，l 和 r 相等，此时这个位置就是目标值应该插入的位置 // 或者是目标值在数组中存在的位置，返回该位置索引 return r; } };