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

题目

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

来源：力扣热题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;
    }
};