二分查找：零基础也能学会的高效查找算法¶

你有没有玩过“猜数字”游戏？比如心里想一个1到100之间的数字，别人每次猜一个数，你只需要说“大了”或“小了”，对方很快就能猜到。这个过程其实就是二分查找的思想——每次通过中间值缩小一半的范围，快速定位目标。

什么是二分查找？¶

二分查找（Binary Search），也叫折半查找，是一种在有序数组中快速定位目标元素的算法。它的核心思想是：通过不断比较中间元素，将查找范围“减半”，直到找到目标或确定不存在。

为什么需要有序数组？¶

假设数组是无序的，比如 [3, 1, 4, 2, 5]，当你猜中间数是4时，无法确定目标在左边还是右边（比如目标是1，4比1大，但左边还有3和1，需要继续比较左边）。只有数组有序时，中间元素才能作为“分界点”，通过比较大小直接判断目标在哪一侧。

二分查找的适用场景¶

二分查找虽然高效，但有明确的适用条件，不是所有场景都适用：

数据必须是有序的（升序或降序，最常见升序）。
数据量较大：当数据量n很大时（比如10000个元素），二分查找的效率比线性查找（逐个比较）高得多。
数据是静态的：如果数据频繁插入、删除或修改，维护有序数组的成本会很高，此时二分查找的优势会被抵消。
需要快速查找：适用于“一次构建、多次查询”的场景（如字典、配置文件）。

查找过程举例¶

以数组 [1, 3, 5, 7, 9, 11, 13] 为例，目标是找 7：

初始范围：左指针 left=0（指向1），右指针 right=6（指向13）。
第一次中间值：mid = (0+6)//2 = 3（数组索引3的元素是7？不对，这里索引3是7吗？等一下，数组是 [1(0), 3(1), 5(2), 7(3), 9(4), 11(5), 13(6)]，所以 mid=3 正好是7！直接找到，返回索引3。

再举一个找9的例子：
- 初始 left=0，right=6，mid=3（元素7）。
- 因为9 > 7，目标在右半部分，所以 left = mid + 1 = 4。
- 新范围：left=4，right=6，mid=(4+6)//2=5（元素11）。
- 因为9 < 11，目标在左半部分，所以 right = mid - 1 = 4。
- 新范围：left=4，right=4，mid=4（元素9），找到目标，返回索引4。

代码实现（迭代法）¶

用Python实现一个基础的二分查找函数，初学者可以直接参考：

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1  # 初始右指针指向最后一个元素
    while left <= right:  # 范围有效：左指针 <= 右指针
        mid = (left + right) // 2  # 计算中间位置（向下取整）
        if nums[mid] == target:
            return mid  # 找到目标，返回索引
        elif nums[mid] < target:
            left = mid + 1  # 目标在右半部分，左指针右移
        else:
            right = mid - 1  # 目标在左半部分，右指针左移
    return -1  # 遍历结束未找到，返回-1

关键细节解释：¶

循环条件：left <= right 确保当范围只剩一个元素时（left=right），仍能判断该元素是否为目标。
中间值计算：mid = (left + right) // 2，Python中整数除法自动向下取整，确保范围正确缩小。
边界处理：如果数组为空（len(nums)=0），直接返回-1；如果目标不存在，最终 left > right 时返回-1。

时间与空间复杂度¶

时间复杂度：每次查找范围减半，次数为 log₂n（n为数组长度），即 O(log n)。例如n=10000时，最多需要14次查找（2¹⁴=16384）。
空间复杂度：迭代实现仅用了left、right、mid三个变量，为 O(1)（常数级）。

常见问题与解决¶

数组中有重复元素怎么办？
基础二分查找可能返回任意一个重复元素的位置。若需找到所有重复元素，可在找到目标后，向左右扩展遍历。
数组长度为1时如何处理？
直接进入循环判断：left=0，right=0，mid=0，比较后返回或结束。
找不到目标时返回-1：明确告知用户未找到，避免返回随机值。

总结¶

二分查找的核心是“减治”——通过每次比较中间值，快速缩小查找范围。记住以下关键点：
- 前提：数组必须有序。
- 优势：大数据量下效率极高（O(log n)），空间占用小（O(1)）。
- 场景：静态有序数据的快速查找（如字典、配置表）。

只要理解“中间值比较+范围调整”的逻辑，二分查找其实很容易掌握。接下来可以尝试自己编写迭代版本的二分查找，解决类似“在有序数组中找特定数”的问题！

二分查找：二分查找的适用场景，零基础也能学会