二分查找实战：x 的平方根与搜索插入位置解析

代码中 mid 的计算使用了 (right - left + 1)，这是为了配合 left = mid 的逻辑。如果向下取整且 left = mid，当 left 和 right 相邻时（如 3 和 4），mid 会一直等于 3，导致死循环。向上取整则能确保区间缩小。

2. 搜索插入位置

问题描述

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

解题思路

我们需要找到一个位置 index，使得该位置左侧的元素都小于 target，右侧的元素都大于等于 target。

设定左边界 left 和右边界 right。根据中间值 nums[mid] 与 target 的比较结果调整边界：

• 若 nums[mid] >= target：说明 mid 落在 [index, right] 区间内，mid 本身可能是结果，或者结果在 mid 左侧。此时新 right 设为 mid。
• 若 nums[mid] < target：说明 mid 落在 [left, index-1] 区间内，结果一定在 mid 右侧。此时新 left 设为 mid + 1。

当 left == right 时，循环结束，此时的 left 即为所求位置。但需注意一种特殊情况：如果 target 大于数组中所有元素，上述逻辑收敛到的 left 会是最后一个元素的索引，实际应返回 size。

C++ 实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if (nums.empty()) return 0; // 处理空数组情况
        int left = 0;
        int right = nums.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 如果 target 大于数组最大值，插入位置应为末尾
        if(target > nums[nums.size() - 1]) {
            return left + 1;
        }
        return left;
    }
};

流程解析

这里的关键在于理解 while(left < right) 的终止条件。当区间长度为 1 时循环停止，此时 left 指向的是第一个大于等于 target 的位置。如果 target 比所有数都大，循环结束后 left 指向最后一个元素，所以需要额外判断是否加 1。

总结

这两道题都是二分查找的典型应用。第一题重点在于处理整数溢出和防止死循环的 mid 取值策略；第二题则考察对边界条件的敏感度，特别是目标值位于数组两端的情况。掌握这些细节，才能在面试中写出健壮的代码。