🔍二分查找（Binary Search）

📖概念讲解

二分查找是一种在有序数组中高效查找目标值的算法。核心思想是：每次把搜索范围缩小一半，而不是一个一个地检查。

算法步骤：

• 设置两个指针 left 和 right，分别指向数组的首尾
• 计算中间位置 mid = (left + right) / 2
• 如果 arr[mid] == target，找到啦！
• 如果 arr[mid] < target，目标在右半部分，令 left = mid + 1
• 如果 arr[mid] > target，目标在左半部分，令 right = mid - 1
• 重复直到 left > right，说明目标不在数组中

时间复杂度：O(log n) — 即使有一百万个数，最多也只需要约 20 次比较！对比线性查找的 O(n) 快得多。

💻代码示例

📝 关键行解释：

• 第 9 行：mid = left + (right - left) / 2 — 为什么不用 (left + right) / 2？因为两个大整数相加可能溢出！left + (right - left) / 2 效果一样但更安全。
• 第 8 行：循环条件是 left <= right（有等号），漏掉等号会漏查最后一个元素！
• 第 14 行：是 mid + 1 而不是 mid，否则当 left == right 时会死循环。

🧩互动小测

📝易错点提醒

🏋️动手练一练

#include <iostream>
using namespace std;

int binarySearch(int nums[], int n, int target) {
    int left = 0, right = n - 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() {
    int nums[] = {1, 3, 5, 7, 9, 11};
    int n = 6, target = 7;
    cout << binarySearch(nums, n, target) << endl;  // 输出: 3
    return 0;
}