编程科技探索

在书堆里找一本书

在一千本乱书里找一本，怎么找最快？程序员有两个妙招——线性搜索和二分搜索。

7-10岁6分钟编程思维 · 算法 · 搜索

想象一下，你有一千本书，要从中找到《小王子》。你会怎么找？一本一本翻？还是用更聪明的办法？这就是程序员每天都在思考的“搜索问题”。搜索算法听起来高大上，其实就是“怎么找东西最快”的学问。

你知道吗

你知道吗？如果用“一本一本翻”的方法，平均要翻 500 本才能找到。但如果书是按字母排好的，用“二分搜索”，最多只要翻 10 次！一千本变十次，这就是算法的威力。

线性搜索：老实办法

最简单的搜索方法叫“线性搜索”——从第一本开始，一本一本看，是不是要找的，不是就换下一本。这个办法一定能找到（只要书在里面），但慢——如果书在最后，你要翻一千次。它的好处是不管书有没有排好都能用，简单可靠。

更聪明的办法叫“二分搜索”，前提是书已经按顺序排好。先翻中间那本——如果它排在你要找的前面，那你要的就在后半部分；如果在后面，就在前半部分。每次都翻“中间”，范围就缩小一半。1000 本 → 500 → 250 → 125 → 62 → 31 → 16 → 8 → 4 → 2 → 1，最多 10 次！

为什么二分搜索这么快？因为它每次都把问题“砍一半”。就像猜数字游戏：你想一个 1 到 100 之间的数，我每次猜中间的数，你告诉我“大了”还是“小了”，最多 7 次就能猜中！这就是“分治”思想——把大问题拆成小问题，一个个解决。计算机里很多聪明算法都用这个思路。

线性搜索：不要求排序，但慢
二分搜索：要求排序，但极快
二分搜索每次把范围缩小一半
数据越多，二分搜索优势越大
很多聪明算法都用“分治”思想

什么时候用哪种？

那是不是永远用二分搜索就好呢？不一定。如果数据本来就乱糟糟的，要先花时间排序才能用二分，可能反而更慢。如果只找一两次，线性搜索就够用了；如果要找很多次，先排序再用二分搜索就划算。程序员要根据情况选最合适的办法，这就是“算法选择”的智慧。

动手试试

不插电小游戏：把 30 张扑克牌数字面朝下排成一排（先按数字大小排好）。用“线性搜索”找一张牌（一张张翻），记录翻了几次。再打乱重排好，用“二分搜索”（每次翻中间，根据大小决定往左还是往右），再记录次数。比一比哪种快？还可以和爸爸妈妈玩“猜数字”游戏：他想一个 1-100 的数，你用二分搜索的方法猜，看几次能猜中。