【Leetcode每日一题】二分查找 - 搜索插入位置（难度⭐）（21）

1. 题目解析

Leetcode链接：35. 搜索插入位置

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

核心在于找到给定目标值要在给定数组下标插入的下标并返回，设计一个O(logn)的算法。

2. 算法原理

a. 分析插入位置左右两侧区间上元素的特点：
当给定一个插入位置坐标 index，根据这个位置的特性，我们可以得出以下结论：

在区间 [left, index - 1] 内的所有元素均小于 target。
而在区间 [index, right] 内的所有元素均大于或等于 target。

b. 设 left 为当前查询的左边界，right 为当前查询的右边界。基于 mid 位置元素的信息，我们来分析下一轮查询的区间：

当 nums[mid] >= target 时，这表示 mid 落在了区间 [index, right] 上。由于 mid 本身及其左侧的部分可能包含最终的结果，所以下一轮的查询区间应该是 [left, mid]。因此，我们将 right 更新为 mid 的位置，并继续查找。
当 nums[mid] < target 时，这意味着 mid 位于区间 [left, index - 1] 上。考虑到 mid 右侧（但不包括 mid 本身）的部分可能包含最终结果，下一轮的查询区间应该是 [mid + 1, right]。因此，我们将 left 更新为 mid + 1 的位置，并继续查找。

c. 这个查找过程会持续进行，直到查询区间的长度变为 1，即 left == right。此时，left 或 right 所在的位置就是我们要找的插入位置。

3.代码实现

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