算法：怎样找得快 · 计算机入门
朋友在 1 到 100 之间想好一个数，只会回答「再大一点」或「再小一点」。怎样最快猜中？
课程目录为什么需要它
算法 Algorithm 就是解决一个问题的一串精确步骤。每个程序都是由算法搭起来的，好的算法和差的算法，可能就是一百万步和二十步的差别。
从这一课开始，你要像程序员一样想问题：不只问能不能做到，还要问要走多少步。
直觉理解
菜谱、去朋友家的路线、系鞋带的步骤，这些都是算法。一个好的算法应该
- 精确：每一步都清清楚楚，不用猜（「加点盐」不精确，「加 2 克盐」才精确），
- 有限：一定会结束，
- 正确：每次都给出对的答案。
猜数游戏的两种算法
一个一个猜。先猜 1，再猜 2，再猜 3……总能猜中，但如果答案是 100，就要猜 100 次。
每次砍一半。先猜正中间的 50。如果朋友说「再大一点」，答案就在 51 到 100 之间：一个问题就排除了一半的可能。再猜剩下部分的中间，75，然后继续。每猜一次，剩下的就少一半：100 → 50 → 25 → 13 → 7 → 4 → 2 → 1。所以 1 到 100 之间的任何数，最多 7 次就能猜中。
问题越大，差距越大。一百万个数，一个一个猜可能要一百万次；每次砍一半，最多 20 次。
砍一半之所以行得通，是因为这些数是排好序的，「再大一点」「再小一点」才能告诉你该留下哪一半。字典和通讯录都按顺序排，也是这个原因。这种每次砍一半的找法叫二分查找 Binary search。
右边的两台机器分别用这两种方法猜。改一改秘密数字，比一比各要猜几次。
定义
算法 Algorithm
An algorithm is a finite list of precise steps that solves a problem.算法是一串有限的、精确的步骤，用来解决一个问题。
二分查找 Binary search
Binary search finds an item in a sorted list by repeatedly checking the middle and throwing away the half that cannot contain it.二分查找在排好序的列表里找东西：每次看正中间那个，然后丢掉不可能包含它的那一半，一直重复。
示例
一个一个猜
动手试试最简单的办法。把秘密数字分别改成 5 和 100 试试。
secret = 73 # change me 改这里
guesses = 0
for guess in range(1, 101):
guesses = guesses + 1
if guess == secret:
break
print("Found", secret, "after", guesses, "guesses")- L1朋友想好的数。
secret = 73 - L3猜 1、2、3……一直到 100。
guess = 1 - L4每猜一次就记一笔。
guesses = 1 - L5猜中了吗？要到 73 才中。
guess = 73 - L7猜 73 用了 73 次。
Found 73 after 73 guesses
每次砍一半
动手试试每次都猜剩下那些数的正中间。试试 1、100 和 50：从来不会超过 7 次。
secret = 73 # change me 改这里
low = 1
high = 100
guesses = 0
while low <= high:
guess = (low + high) // 2
guesses = guesses + 1
if guess == secret:
print(guess, "-> got it!")
break
elif guess < secret:
print(guess, "-> higher")
low = guess + 1
else:
print(guess, "-> lower")
high = guess - 1
print("Guesses:", guesses)- L2一开始，1 到 100 都有可能。
low = 1, high = 100 - L6猜中间的数（向下取整）。
guess = 50 - L1250 太小：答案更大。
50 -> higher - L13丢掉 1 到 50。
low = 51 - L651 到 100 的中间。
guess = 75 - L1675 太大：丢掉 75 到 100。
high = 74 - L9再砍几次，就落到了 73。
73 -> got it! - L176 次，而不是 73 次。
Guesses: 6
问题变大时
动手试试每种规模下，两种方法最坏要猜几次。数量多 10 倍，一个一个猜就多 10 倍，砍一半只多大约 3 次。
for size in [100, 1000, 10000, 100000, 1000000]:
steps = 0
left = size
while left > 0:
left = left // 2
steps = steps + 1
print(size, "numbers: one by one up to", size, "| halving at most", steps)- L1范围一个比一个大。
size = 100 - L5一直砍一半直到不剩，数一数砍了几次。
100, 50, 25, 12, 6, 3, 1 - L7100 个数：最多 7 次。
100 … halving at most 7 - L7一百万个数：最多 20 次。
1000000 … halving at most 20
常见错误
砍一半的前提是排好序
如果数或者名字是乱的，看中间那个也没法知道该留哪一半。那就只能老老实实一个一个找。
「能用」还不够
两种方法都一定能找到。区别在于要走多少步，问题一大，这个差别就非常要紧。
步骤必须精确
「猜个差不多中间的数」不是算法里的一步，「猜（最小 + 最大）÷ 2，向下取整」才是。计算机需要精确的版本。
小测验
1. 答案在 1 到 100 之间。你猜 50，朋友说「再小一点」。还有哪些数有可能？
查看答案
答案：A
「再小一点」说明答案比 50 小，只剩 1 到 49。猜一次就排除了一半。
2. 下面哪个可以用砍一半的方法来找？
查看答案
答案：B
只有字典是排好序的。从中间翻开，就知道要找的字在前一半还是后一半。
3. 用砍一半的方法，猜 1 到 1000 之间的数最多要几次？
查看答案
答案：A
1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1：大约砍 10 次。
要点
- 算法是一串精确、有限、能解决问题的步骤。
- 同一个问题，不同的算法要走的步数可能差得非常远。
- 二分查找每一步都把可能性砍掉一半，但只能用在排好序的数据上。
动手练习
3 道小练习：先想一想，再动手改一改看看结果，最后自己来一次。提交马上告诉你对不对。
- 想一想下一次猜几？
答案在 1 到 100 之间。你猜了 50，朋友说「再大一点」；又猜了 75，朋友说「再小一点」。
按砍一半的方法（猜中间，向下取整），下一次猜几？
- 改一改范围变大了
朋友现在从 1 到 1000 里选数，秘密数字是 999。机器还是只在 1 到 100 里找，所以永远找不到：先按运行看看。
改一改范围，让机器找到 999。秘密数字保持不变。
- 自己来数一数猜几次
在 1 到 16 里用砍一半的方法猜：每次猜中间，向下取整。秘密数字是 16。
猜几次能猜中？先在纸上算一算，再用右边的「每次砍一半」机器检查（改
secret和high）。
本课术语
| 术语 | 中文 | 英文定义 |
|---|---|---|
| Algorithm | 算法 | A finite list of precise steps that solves a problem. |
| Linear search | 顺序查找 | Checking items one by one from the start until you find the one you want. |
| Binary search | 二分查找 | Finding an item in a sorted list by checking the middle and keeping only the half that can contain it. |
| Sorted | 有序 | Arranged in order, such as smallest to largest or A to Z. |