二分查找中的分治

学习目标

本节用二分查找理解分治思想。

二分查找适用于有序数据。它每次查看中间元素，然后根据大小关系排除一半搜索范围。虽然它没有复杂的合并过程，但它清晰体现了“把问题规模不断缩小”的思想。

---

二分查找的前提

二分查找的前提是数据已经有序。

如果数组没有排序，就不能通过比较中间元素来判断目标值在左半边还是右半边。

例如：

有序数组:  2  5  8  12  16  23  38
目标值:    16

先检查中间元素 12。因为 16 大于 12，所以目标值如果存在，只可能在右半部分。

---

二分查找的过程

二分查找维护一个搜索区间，通常用 left 和 right 表示左右边界。

1. 计算中间位置 mid。

2. 比较中间元素和目标值。

3. 如果中间元素等于目标值，查找成功。

4. 如果中间元素小于目标值，丢弃左半部分。

5. 如果中间元素大于目标值，丢弃右半部分。

6. 重复以上过程，直到找到目标或区间为空。

每一步都会把搜索范围缩小到原来的一半左右。

---

迭代版本二分查找

C++

int binarySearch(const vector<int>& numbers, int target) {
    int left = 0;
    int right = numbers.size() - 1;

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

        if (numbers[mid] == target) {
            return mid;
        }

        if (numbers[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Java

int binarySearch(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;

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

        if (numbers[mid] == target) {
            return mid;
        }

        if (numbers[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

Python

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if numbers[mid] == target:
            return mid

        if numbers[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

C#

int BinarySearch(int[] numbers, int target)
{
    int left = 0;
    int right = numbers.Length - 1;

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

        if (numbers[mid] == target)
        {
            return mid;
        }

        if (numbers[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return -1;
}

这四段代码都使用同一个边界规则：只要 left <= right，区间中就还有候选元素。

---

为什么中点这样计算

代码中常写：

mid = left + (right - left) / 2

而不是简单写成：

mid = (left + right) / 2

原因是 left + right 在某些语言和极大数据范围下可能发生整数溢出。虽然在很多学习示例中不容易遇到，但养成更稳妥的写法是好习惯。

---

复杂度分析

每次查找都会把范围缩小一半。

如果初始有 $n$ 个元素，经过一次比较后剩下大约 $n / 2$ 个，再经过一次剩下 $n / 4$ 个。经过若干次后，范围会缩小到 1。

因此，二分查找的时间复杂度是 $O(\log n)$。

迭代版本只使用少量变量，额外空间复杂度是 $O(1)$。

---

常见边界错误

二分查找最容易出错的是边界更新。

例如：

• left <= right 和 left < right 混用。
• right = mid 和 right = mid - 1 混用。
• 找到目标后应该返回还是继续查找边界没有想清楚。
• 空数组没有正确处理。

学习阶段建议先掌握最基础的“查找某个值是否存在”的版本，再学习查找左边界、右边界等变体。

---

本节小结

二分查找通过每次排除一半候选范围，把查找复杂度从线性级降低到对数级。

它的前提是数据有序。实现时要特别注意边界条件和中点计算。二分查找是理解分治思想和对数复杂度的经典例子。