查找：线性查找与二分查找

这是什么：查找 = 在一批数据里定位目标，本章给两种经典思路：线性查找（一个个翻）和二分查找（对着砍一半）。

为什么用：上一章的通讯录问题来了：从一堆数据里找出目标，是最常见的算法任务。不讲究方法，一个一个翻，十万条数据能翻到你怀疑人生。

如何用：本章先写一个最朴素的线性查找，再写一个要求列表有序的二分查找，比比谁快。

线性查找：一页页翻

最朴素的办法：从第一个开始挨个比对，找到就停。

nums = [7, 3, 9, 1, 5]

def linear_search(nums, target):
    for i, num in enumerate(nums):
        if num == target:
            return i          # 找到了，返回下标
    return -1                 # 翻完都没有

print(linear_search(nums, 9))
print(linear_search(nums, 4))

你会看到：

2
-1

9 在下标 2 的位置；4 不在列表里，返回 -1（约定俗成的"没找到"信号）。它一个不漏，但对 n 个数据，最坏要翻 n 次——O(n)。

二分查找：翻中间

翻纸质词典查"猫"字，没人从"阿"开始翻——你直接翻中间，看目标在前面还是后面，一次排除一半，再翻剩下那半的中间……这就是二分查找。

代价只有一个：列表必须先排好序。词典按拼音排、通讯录按字母排，无序列表没法"排除一半"。

nums = [1, 3, 5, 7, 9, 11, 13]

def binary_search(nums, target):
    left, right = 0, 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

print(binary_search(nums, 11))
print(binary_search(nums, 4))

你会看到：

5
-1

快多少？100 万数据见分晓

20 次对比 100 万次，约等于线性查找的五万分之一。亲手数一数：

import math

n = 1_000_000
print(n, "条数据：")
print("线性最坏要", n, "次")
print("二分最多", math.ceil(math.log2(n)), "次")

你会看到：

1000000 条数据：
线性最坏要 1000000 次
二分最多 20 次

一句带过：Python 自带的查找

日常查"在不在"，直接用内置的：4 in nums 返回 True/False；nums.index(4) 返回下标（找不到会报错）。写业务代码优先用它们——但理解了上面两个手写版，你才知道快慢从哪来。

逐概念解读

记忆口诀

线性一页页，二分砍一半；想砍先排序，无序只能翻。

动手改

1. 用 binary_search 查列表里没有的数 8，在纸上走一遍左右指针的移动，验证返回 -1
2. 加个计数变量，数一数查 13（最后一个数）要循环几轮
3. 生成 1~100 的有序列表 list(range(1, 101))，用二分找 87，看看找了几轮

下一章：排序，"列表必须有序"？那就自己排 🐸