查找

它是什么

查找 就是找某个目标在不在。 在哪一个位置也可以算查找。

书包里找橡皮。 名单里找同学。 字典里找一个字。 这些都是查找。

电脑最常在 列表 里找。 办法不同，快慢不同。 前提也不同。

两种入门算法：

• 顺序查找：从左到右一个一个问
• 二分查找：在已经排好序的一排里，反复看中间、丢掉一半

它们都属于 算法。

名字从哪来

查找的英文是 search。 日常就是「搜寻」。

顺序查找也叫线性查找。 线性的意思是：沿着一条线往前走，不跳。

二分查找的英文是 binary search。 binary 表示「二」。 每一次把范围切成两半，留下可能的那一半。

图书馆把书按编号排上架，才能快速定位。 字典按拼音或部首排列，才能少翻很多页。 「先排序，再折半」不是电脑独有的发明，是人早就在用的办法。

它怎么工作

顺序查找

从左到右一个一个比。 最朴素，也好懂。 列表不必先排序。

# 顺序查找
nums = [3, 8, 2, 5]
target = 5
found = False
for n in nums:
    if n == target:
        found = True
        break
print(found)

找到可以用 break 提前停。 找不到就保持 False。

最倒霉时，目标在最后，或根本不在。 那时几乎每个格子都要问一遍。

二分查找

前提：已经按顺序排好。 每次看中间那个。 太大去左边。 太小去右边。 范围越缩越小。

# 二分查找：列表已排序
nums = [1, 3, 5, 7, 9]
target = 7
left = 0
right = len(nums) - 1
found = False
while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
        found = True
        break
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
print(found)

mid 是中间下标。 // 2 保证是整数位置。 这是 while 的典型用法。 也用到 整除。

没排序时，不要直接二分。 可以先 sorted，或改用顺序查找。 排序本身也要花时间。 东西很少时，一个一个找往往更省事。

in 运算符在列表里，通常也是顺序问过去。 写法短，思路仍是「一个一个比」。

生活里在哪里

• 书架：如果书是乱堆的，你只能一本本翻。那是顺序查找。
• 图书馆：书按号排好，你可以先走到大概的架，再缩小。有点像二分的精神。
• 猜数字：人家说「更大」「更小」，你每次从中间猜，就是在折半。
• 点名册：没按座位排时，只能从上往下扫名字。
• 字典 App：背后往往先排序，再快速定位。

CS Unplugged 里有一个经典游戏：在已经排好的天平或卡片中找目标，体会「每次丢掉一半」。

和相近概念的差别

查找是在已有的一堆里问「在不在 / 在哪」。 枚举常常是把可能的答案都生成一遍再检查。 二者都能用 循环 和 分支，问题不同。

排序是把队伍排整齐。 二分查找要求队伍已经整齐。 先排队，再折半。 不要把排序和查找当成同一件事。

list.index(x) 也能找位置。 找不到会报错。 自己写循环时，常常用 found 标记，更方便处理「没有」。

常见误会

误会 1：没排序就二分。

中间那个不能代表左右两边的大小关系。 办法会错。

误会 2：right 写成 len(nums)。

最后一个下标是长度减 1。 取到长度本身，会 IndexError。

误会 3：中间位置用普通除法 /。

得到小数下标，列表不认。 要用 //。

误会 4：找到以后既不 break，也不记录。

循环白跑。 结果也可能被后面的比较冲掉。

误会 5：二分一定总是更好。

东西很少，或完全没排序，顺序查找更直接。 工具要配场合。

想知道更多

• 书：阿迪特亚·巴尔加瓦《算法图解》。第一章就用电话簿、猜数字讲二分，可以和家长一起看图画。
• 书：潘洪波《小学生 Python 趣味编程》（用名单、猜数字体会「一个一个找」和「缩小范围」）。
• 电影：《隐藏人物》（Hidden Figures）。和家长一起看：把大问题拆成清楚步骤，才能找得又准又稳。