征服力扣704题：三步掌握经典二分查找算法

题目重解

我们面对的是算法领域最经典的二分查找问题：在一个已排序的整数数组中，快速定位目标值的位置。就像在一本按字母顺序排列的字典中查找单词，我们不需要逐页翻阅，而是通过不断折半的方式快速缩小搜索范围，这正是二分查找的精髓所在。

解题思路解析

用递归实现二分查找：

‌基准情况1‌：当搜索范围缩小到单个元素时（l == r），直接比较该元素

‌基准情况2‌：当范围剩两个元素时（l+1 == r），分别比较这两个元素

‌递归过程‌：计算中间位置，根据中间值与目标值的关系决定向左或向右继续搜索

整个过程就像是在玩"猜数字"游戏，每次猜测都能排除一半的错误答案，直到找到正确答案或确认不存在。递归的终止条件和边界处理确保了搜索的正确性和完整性。

代码注释版

class Solution {
public:
    int binaryselect(vector<int> a, int num, int l, int r) {
        // 情况1：搜索范围缩小到单个元素
        if (l == r) {
            if (a[l] == num)
                return l;  // 找到目标
            else
                return -1; // 未找到
        }
        // 情况2：搜索范围剩两个元素
        if (l + 1 == r) {
            if (a[l] == num)
                return l;
            else if (a[r] == num)
                return r;
            else
                return -1;
        }
        // 计算中间位置
        int mid = (l + r) / 2;
        if (a[mid] == num)
            return mid;  // 直接命中
        else if (a[mid] < num)
            return binaryselect(a, num, mid + 1, r); // 向右半部分继续搜索
        else
            return binaryselect(a, num, l, mid - 1); // 向左半部分继续搜索
    }
    
    int search(vector<int>& nums, int target) {
        // 从整个数组范围开始搜索
        return binaryselect(nums, target, 0, nums.size() - 1);
    }
};