Day 20

二分查找（Binary Search） 是一种在有序数组中查找特定元素的高效算法。它的核心思想是通过不断将搜索区间减半来缩小查找范围，因此也被称为折半查找。

1. 核心思想

二分查找的工作流程可以概括为以下几点：

确定范围：首先，定义整个数组为初始的搜索区间 [left, right]。
找到中点：计算当前区间的中间位置 mid = left + (right - left) / 2。（使用 left + (right - left) / 2 而不是 (left + right) / 2 是为了防止 left + right 时发生整数溢出）。
比较中点值：情况一（找到目标）：如果 nums[mid] 等于目标值 target，则查找成功，返回 mid。情况二（目标在右半部分）：如果 nums[mid] 小于 target，说明目标值只可能在 mid 的右侧。因此，将搜索区间更新为 [mid + 1, right]。情况三（目标在左半部分）：如果 nums[mid] 大于 target，说明目标值只可能在 mid 的左侧。因此，将搜索区间更新为 [left, mid - 1]。
重复过程：重复步骤 2 和 3，直到找到目标值，或者 left > right（此时说明区间为空，目标值不存在于数组中）。

2. 算法步骤（迭代实现）

plaintext

函数 binarySearch(nums, target):
    left = 0
    right = nums.length - 1

    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            return mid  # 找到目标，返回索引
        elif nums[mid] < target:
            left = mid + 1  # 目标在右半部分
        else:
            right = mid - 1 # 目标在左半部分

    return -1  # 未找到目标

3. 示例

假设我们要在数组 nums = [-1, 0, 3, 5, 9, 12] 中查找目标值 9。

初始状态: left = 0, right = 5mid = 0 + (5 - 0) / 2 = 2nums[2] 是 3。因为 3 < 9，所以目标在右半部分。更新 left = mid + 1 = 3。
第一次迭代后: left = 3, right = 5mid = 3 + (5 - 3) / 2 = 4nums[4] 是 9。因为 9 == 9，查找成功！返回索引 4。

4. C++ 实现

二分查找通常有两种实现方式：迭代和递归。迭代方式更为常用，因为它避免了递归的函数调用开销。

迭代实现

cpp

运行

#include <iostream>
#include <vector>

/**
 * @brief 使用迭代法实现二分查找
 * @param nums 有序的整数向量
 * @param target 要查找的目标值
 * @return int 如果找到，返回目标值的索引；否则返回 -1
 */
int binarySearchIterative(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        // 计算中点，防止溢出
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid; // 找到目标
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标在右半部分
        } else {
            right = mid - 1; // 目标在左半部分
        }
    }

    return -1; // 未找到目标
}

int main() {
    std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;

    int index = binarySearchIterative(nums, target);

    if (index != -1) {
        std::cout << "目标值 " << target << " 在索引 " << index << " 处找到。" << std::endl;
    } else {
        std::cout << "未找到目标值 " << target << "。" << std::endl;
    }

    target = 2;
    index = binarySearchIterative(nums, target);
    if (index != -1) {
        std::cout << "目标值 " << target << " 在索引 " << index << " 处找到。" << std::endl;
    } else {
        std::cout << "未找到目标值 " << target << "。" << std::endl;
    }

    return 0;
}

递归实现

cpp

运行

#include <iostream>
#include <vector>

/**
 * @brief 二分查找的递归辅助函数
 * @param nums 有序的整数向量
 * @param target 要查找的目标值
 * @param left 当前搜索区间的左边界
 * @param right 当前搜索区间的右边界
 * @return int 如果找到，返回目标值的索引；否则返回 -1
 */
int binarySearchRecursiveHelper(const std::vector<int>& nums, int target, int left, int right) {
    // 递归终止条件：区间为空
    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (nums[mid] == target) {
        return mid; // 找到目标
    } else if (nums[mid] < target) {
        // 递归地在右半部分查找
        return binarySearchRecursiveHelper(nums, target, mid + 1, right);
    } else {
        // 递归地在左半部分查找
        return binarySearchRecursiveHelper(nums, target, left, mid - 1);
    }
}

/**
 * @brief 使用递归法实现二分查找
 * @param nums 有序的整数向量
 * @param target 要查找的目标值
 * @return int 如果找到，返回目标值的索引；否则返回 -1
 */
int binarySearchRecursive(const std::vector<int>& nums, int target) {
    return binarySearchRecursiveHelper(nums, target, 0, nums.size() - 1);
}

int main() {
    std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;

    int index = binarySearchRecursive(nums, target);

    if (index != -1) {
        std::cout << "目标值 " << target << " 在索引 " << index << " 处找到。" << std::endl;
    } else {
        std::cout << "未找到目标值 " << target << "。" << std::endl;
    }

    return 0;
}

5. 复杂度分析

时间复杂度：每次比较后，搜索区间的大小都会减半。如果数组大小为 n，那么查找次数 k 满足 n / (2^k) <= 1。解得 k = log2(n)。因此，二分查找的时间复杂度为 O(log n)。这是一个非常高效的时间复杂度，远优于线性查找的 O (n)。
空间复杂度：迭代实现：只使用了几个额外的变量（left, right, mid），所以空间复杂度为 O(1)。递归实现：递归调用会占用调用栈的空间。最坏情况下，递归深度为 log2(n)，所以空间复杂度为 O(log n)。

6. 应用场景与变种

前提条件：二分查找的绝对前提是数组必须是有序的。如果数组无序，必须先进行排序（如使用 std::sort），但排序本身的时间复杂度为 O (n log n)。
C++ 标准库：C++ 标准库的 <algorithm> 头文件中提供了 std::binary_search, std::lower_bound, std::upper_bound 等函数，它们都是基于二分查找实现的。在实际项目中，应优先使用标准库函数。
变种问题：二分查找的思想非常灵活，可以解决许多看似不相关的问题，例如：寻找第一个 / 最后一个等于目标值的元素。寻找第一个大于 / 大于等于目标值的元素（std::lower_bound）。寻找最后一个小于 / 小于等于目标值的元素。在旋转排序数组中查找。二分答案：在一个可能的解空间（如整数范围）中，通过二分查找来寻找满足特定条件的最优解。