如果牌堆中的纸牌不是按顺序排列的，那就没有比线性查找更快的查找方法了。我们必须查看每张纸牌，因为除此之外我们无法确定要找的纸牌是不是在其中。 但是查词典时，我们并不是从头到尾、一个词一个词的查。因为单词是以字母顺序排列的，所以我们可以使用类似于二分查找的算法： 1. 从中间某个位置开始。 2. 在这一页上选择一个单词，并用这个单词和我们要查找的单词比较。 3. 如果这就是我们要找的单词，结束。 4. 如果我们要找的单词在这一页上的单词之后，翻到后面某页并回到第2步。 5. 如果我们要找的单词在这一页上的单词之前，翻到词典前面某页并回到第2步。 如果遇到了这种情况，某页上有两个相邻的单词，而要找的单词应该在它们之间，这时即可确定词典中没要我们要查的单词。唯一的例外就是单词印错地方了，但这就与单词按字母顺序排列的假设冲突了。 在牌堆这个例子中，如果知道纸牌是有序摆放的，我们就能写一个更快的find函数。编写二分查找最好的方法是利用递归函数，因为二分自然而然是递归的。 窍门是编写findBisect函数，它以两个索引值low和high为参数，用以确定要查找的向量的一段（包括low和high指定的元素）。 1. 要在向量中查找，选择low和high之间的一个索引，我们称之为mid。将mid指定的纸牌与我们要查找的牌相比。 2. 如果找到，结束。 3. 如果mid处的纸牌比要找的牌大，继续在low和mid-1确定的区间中查找。 4. 如果mid处的纸牌比要找的牌小，继续在mid+1和high确定的区间中查找。 可以怀疑第3步和第4步看起来像递归调用。我们将其转化为C++代码，看起来是这个样子的： ~~~ int findBisect (const Card& card, const apvector<Card>& deck, int low, int high) { int mid = (high + low) / 2; // 如果找到了纸牌，返回其index if (equals (deck[mid], card)) return mid; // 否则，将纸牌与中间的纸牌比较 if (deck[mid].isGreater (card)) { // 查找纸牌的前一半 return findBisect (card, deck, low, mid-1); } else { // 查找纸牌的后一半 return findBisect (card, deck, mid+1, high); } } ~~~ 虽然这段代码已经包含了二分查找的核心，但还是缺点什么。按照当前代码，如果要找的纸牌不再牌堆中，它会一直递归下去。我们需要找到一种方法来检查这一条件并做出适当的处理（通过返回-1）。 识别出目标纸牌不在牌堆中最简单的方法是，牌堆中没有纸牌，也就是high小于low的情况。当然，牌堆中仍然有牌，我的意思是由low和high指定的段中没有纸牌。 添加了high ~~~ int findBisect (const Card& card, const apvector<Card>& deck, int low, int high) { cout << low << ", " << high << endl; if (high < low) return -1; int mid = (high + low) / 2; if (equals (deck[mid], card)) return mid; if (deck[mid].isGreater (card)) { return findBisect (card, deck, low, mid-1); } else { return findBisect (card, deck, mid+1, high); } } ~~~ 我在开头添加了一行输出语句，这样我们能查看递归调用序列并说服我们递归会走到基本条件。尝试下面代码 ~~~ cout << findBisect (deck, deck[23], 0, 51)); ~~~ 其输出如下： ~~~ 0, 51 0, 24 13, 24 19, 24 22, 24 I found the card at index = 23 ~~~ 然后，我编造了1张不在牌堆中的牌——方块15，然后试一下查找它，输出如下： ~~~ 0, 51 0, 24 13, 24 13, 17 13, 14 13, 12 I found the card at index = -1 ~~~ 这些测试并不能证明程序的正确性，其实再多的数据也无法证明程序是正确的。但是看几个例子并检验代码，也许可以说服你自己。 递归调用的次数相当少，通常是6或7次。也就是说equals函数和isGreater函数只需要调用6或7次，而线性查找最多要调用52次。一般而言，二分查找比线性查找快的多，尤其是向量中元素数目很多时，效果更为明显。 递归程序中两个常见错误，一个是忘记了包含基本条件，另一个是递归调用永远取不到基本条件。每个错误都会导致无穷递归，这种情况下C++最终会出现运行时错误。