力扣35：二分法在搜索插入位置中的运用

有序数组的定位

在一个严格递增的数字序列中，每个元素都有其确定的位置。当新元素试图加入时，我们需要回答两个问题：它是否已经存在？如果不存在，它应该插入在哪里？这道题要求我们在O(log n)时间内完成这个精确定位。

递归二分法的边界

递归处理逻辑：

‌1.双元素区间处理‌：当搜索范围缩小到2个元素时（l+1 == r-1），通过三重判断确定插入位置：位于中间、等于右边界或小于左边界

‌2.单元素区间终结‌：当区间只剩1个元素时（l == r-1），直接比较大小决定插入左侧还是右侧

‌3.动态区间调整‌：通过中点比较决定搜索方向，特别注意处理mid-1<0的边界情况，避免数组越界

代码及注释

class Solution {
public:
    // 递归核心：在半开区间[l,r)中定位target
    int binaryselect(vector<int> a, int num, int l, int r) {
        // 处理三元素区间特殊情况
        if (l + 1 == r-1) { // 实际处理2个有效元素
            if (a[l] < num && a[r-1] > num) 
                return l+1;  // 插入两元素之间
            else if(a[r-1] == num) 
                return r-1; // 命中右边界
            else if(a[l] >= num) 
                return l;   // 需插入左边界前
            return r;       // 插入右边界后
        }
        // 处理单元素区间
        else if(l == r-1) {
            return a[l] < num ? l+1 : l; // 决定插入左右
        }
        // 常规二分处理
        else {
            int mid = (l + r-1) / 2; // 中点计算
            if (a[mid] == num) 
                return mid; // 直接命中
            // 搜索右侧区间[mid+1,r)
            else if(a[mid] < num) 
                return binaryselect(a, num, mid + 1, r);
            // 搜索左侧区间[l,mid)
            else {
                if(mid-1 < 0) return l; // 左边界保护
                return binaryselect(a, num, l, mid);
            }
        }
    }

    int searchInsert(vector<int>& nums, int target) {
        // 启动递归，初始区间[0,n)
        return binaryselect(nums, target, 0, nums.size());
    }
};