二分查找：原理、图解与 C++ 实战

一、什么是二分查找

二分查找（Binary Search）是一种在有序序列上高效定位目标的算法。它的核心思想很简单：每次取中间元素与目标比较，根据单调性排除掉一半的区间，在剩下的一半里继续找。

它的前提是单调性：要么序列本身有序，要么存在某个划分点使得左半边满足某性质、右半边不满足。只要能找到这样的"二段性"，就能用二分。

1.1 二分的三种常见形态

二、核心原理与图解

二分查找的每一次迭代都做三件事：取中点 → 比较 → 砍半。关键是每次砍掉的"半"必须是确定不含答案的那一半，这依赖单调性来保证。

2.1 区间收缩过程

以在有序数组 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 中查找 target = 11 为例：

2.2 三种边界模板对比

二分的难点在于区间约定不同，循环条件和收缩方式也不同。下面是三种主流写法的对比图：

2.3 复杂度分析

三、通用模板

下面给出三种区间约定的完整模板，按需选用。建议固定一种记熟（推荐左闭右闭），不要在题目里来回切换写法。

// ============= 模板 1：左闭右闭 [l, r]（推荐，最直观）=============
int binarySearchClosed(const vector<int>& nums, int target) {
    int l = 0, r = (int)nums.size() - 1;
    while (l <= r) {                  // 注意是 <=，因为 [l,r] 闭区间合法
        int mid = l + (r - l) / 2;    // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;  // 未找到
}

// ============= 模板 2：左闭右开 [l, r)（STL 风格）=============
int binarySearchHalfOpen(const vector<int>& nums, int target) {
    int l = 0, r = (int)nums.size();   // r 初始为 size，不取该下标
    while (l < r) {                    // 注意是 <
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid;               // 不 -1，因为 r 是开区间
    }
    return -1;
}

// ============= 模板 3：左开右开 (l, r)（适合求左右边界）=============
// 适合"找第一个满足条件的位置"或"最后一个满足条件的位置"
int lowerBound(const vector<int>& nums, int target) {
    // 找第一个 >= target 的下标
    int l = -1, r = (int)nums.size();  // 开区间，l=-1, r=n
    while (l + 1 < r) {               // 区间内至少还有一个元素
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) l = mid;  // 把 mid 留在左开区间
        else r = mid;                      // nums[mid] >= target，mid 可能是答案
    }
    return r;  // r 就是第一个 >= target 的下标
}

四、示例一：在有序数组中查找目标值

题目（基础）：给定一个升序数组 nums 和目标值 target，返回 target 在数组中的下标，不存在则返回 -1。

4.1 思路与图解

这是二分最基础的形态：精确查找。每次比较 nums[mid] 与 target，相等就返回 mid，不等就根据大小关系砍掉一半。

4.2 C++ 代码

#include <vector>
using namespace std;

// 在升序数组中查找 target，返回下标，找不到返回 -1
int search(const vector<int>& nums, int target) {
    int l = 0, r = (int)nums.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;     // 防溢出写法
        if (nums[mid] == target) {
            return mid;                  // 命中
        } else if (nums[mid] < target) {
            l = mid + 1;                  // target 在右半边
        } else {
            r = mid - 1;                  // target 在左半边
        }
    }
    return -1;  // 没找到
}

五、示例二：搜索旋转排序数组（LeetCode 33）

题目：一个升序数组在某个下标处被旋转（例如 [0,1,2,4,5,6,7] 旋转成 [4,5,6,7,0,1,2]）。给定旋转后的数组，查找 target，返回下标，不存在返回 -1。要求 O(log n)。

5.1 思路：先判断哪半边有序

旋转数组的难点在于整体无序但局部有序。关键观察：取 mid 后，至少有一半是单调的。先判断左半 [l, mid] 是否有序（nums[l] <= nums[mid]），再判断 target 是否落在有序的那半边，据此决定收缩方向。

5.2 C++ 代码

#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int l = 0, r = (int)nums.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;

        // 关键：判断左半 [l, mid] 是否有序
        if (nums[l] <= nums[mid]) {
            // 左半有序，看 target 是否落在左半
            if (nums[l] <= target && target < nums[mid]) {
                r = mid - 1;   // 在左半
            } else {
                l = mid + 1;   // 在右半
            }
        } else {
            // 右半 [mid, r] 有序
            if (nums[mid] < target && target <= nums[r]) {
                l = mid + 1;   // 在右半
            } else {
                r = mid - 1;   // 在左半
            }
        }
    }
    return -1;
}

六、示例三：寻找两个正序数组的中位数（LeetCode 4）

题目：给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2，求它们合并后的中位数。要求时间复杂度 O(log(m+n))。

6.1 思路：二分较短数组的分割点

暴力做法是合并后取中位数，O(m+n)。要 O(log) 必须二分。核心思想是：在两个数组上各画一条分割线，使得左半部分元素总数 = (m+n+1)/2，且左半最大值 ≤ 右半最小值。这样中位数就直接来自分割线两侧。

6.2 C++ 代码

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    // 保证 nums1 是较短的那个，这样二分次数是 O(log(min(m,n)))
    if (nums1.size() > nums2.size()) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int m = nums1.size(), n = nums2.size();
    int totalLeft = (m + n + 1) / 2;  // 左半部分元素总数

    // 在 nums1 的 [0, m] 范围内二分找分割点 i
    int l = 0, r = m;
    while (l <= r) {
        int i = l + (r - l) / 2;       // nums1 分割点：前 i 个进左半
        int j = totalLeft - i;          // nums2 分割点：前 j 个进左半

        // 取分割线两侧的四个关键值（处理边界）
        int nums1LeftMax  = (i == 0) ? INT_MIN : nums1[i - 1];
        int nums1RightMin = (i == m) ? INT_MAX : nums1[i];
        int nums2LeftMax  = (j == 0) ? INT_MIN : nums2[j - 1];
        int nums2RightMin = (j == n) ? INT_MAX : nums2[j];

        if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
            // 找到合法分割
            if ((m + n) % 2 == 1) {
                return (double)max(nums1LeftMax, nums2LeftMax);
            } else {
                return (max(nums1LeftMax, nums2LeftMax)
                      + min(nums1RightMin, nums2RightMin)) / 2.0;
            }
        } else if (nums1LeftMax > nums2RightMin) {
            r = i - 1;  // nums1 分得太靠右，往左找
        } else {
            l = i + 1;  // nums2LeftMax > nums1RightMin，往右找
        }
    }
    return 0.0;  // 不会走到
}

七、总结与适用场景

典型题目清单

• LeetCode 704：二分查找（基础精确查找）
• LeetCode 35：搜索插入位置（左边界）
• LeetCode 34：在排序数组中查找元素的第一个和最后一个位置（左右边界）
• LeetCode 33：搜索旋转排序数组（旋转数组）
• LeetCode 81：搜索旋转排序数组 II（含重复）
• LeetCode 153/154：寻找旋转排序数组中的最小值
• LeetCode 4：寻找两个正序数组的中位数（双数组分割）
• LeetCode 69：x 的平方根（二分答案）
• LeetCode 875：爱吃香蕉的珂珂（二分答案）
• LeetCode 410：分割数组的最大值（二分答案 + 贪心）