二分查找

#二分查找

• 什么是二分查找
• 猜数字游戏
• 操作步骤
• Python 实现
• 时间复杂度
• 使用条件

#什么是二分查找

二分查找是一种高效的查找算法，每次比较都将查找范围缩小一半。前提是数据必须有序。

就像在电话簿中找人名以 K 打头的人——你不会从第一页开始翻，而是从中间开始，因为你知道 K 大概在中间。

#猜数字游戏

你想一个 1～100 的数字，我来猜。每次猜完你告诉我「大了」「小了」或「对了」。

简单查找（傻找）：从 1 开始猜，1、2、3... 如果数字是 99，要猜 99 次。

二分查找：从 50 开始猜。

猜 50 → 你说「小了」  → 排除 1~50（51~100 中找）
猜 75 → 你说「大了」  → 排除 76~100（51~74 中找）
猜 63 → 你说「小了」  → 排除 51~63（64~74 中找）
猜 69 → 你说「大了」  → 排除 70~74（64~68 中找）
猜 66 → 你说「对了」  → 5 次猜到！

或者最坏情况：7 次之内一定能猜到（log₂100 ≈ 7）

每次猜测都排除一半的数字！对于 240 000 个单词的字典，简单查找最多 240 000 步，二分查找只需 18 步。

#操作步骤

在有序数组 1 2 3 4 5 6 7 8 9 中查找 6：

第1轮: 查找范围 [1 2 3 4 5 6 7 8 9]
       中间值 = 5
       5 < 6 → 6 在右边

  1  2  3  4 [5] 6  7  8  9   →   6  7  8  9
              ↑ 中间               剩下右半部分

第2轮: 查找范围 [6 7 8 9]
       中间值 = 7
       7 > 6 → 6 在左边

  6 [7] 8  9   →   6
     ↑ 中间       剩下左半部分

第3轮: 查找范围 [6]
       中间值 = 6
       6 = 6 → 找到了！

只比较了 3 次（log₂9 ≈ 3），比线性查找最多 9 次快得多。

#Python 实现

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid        # 找到了，返回索引
        if guess > item:
            high = mid - 1    # 猜大了，往左找
        else:
            low = mid + 1     # 猜小了，往右找
    return None               # 没找到

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))   # => 1
print(binary_search(my_list, -1))  # => None

#时间复杂度

数据量越大，二分查找的优势越明显。40 亿个元素只需 32 步！

#使用条件

二分查找必须满足：

1. 数据存储在数组中（需要随机访问）
2. 数据已经排好序

如果数据无序，需要先排序（排序本身需要 O(n log n)），之后才能用二分查找。如果需要频繁添加数据，每次添加后维护有序性的成本较高，这种场景更适合用哈希表（O(1) 查找）。

#小结

• 二分查找每次将查找范围减半，时间复杂度 O(log n)
• 前提：数据有序且存储在数组中
• 40 亿个元素只需 32 步，远胜线性查找
• 如果添加频繁，考虑用哈希表代替