加载中...

12.9 二分查找

如果牌堆中的纸牌不是按顺序排列的，那就没有比线性查找更快的查找方法了。我们必须查看每张纸牌，因为除此之外我们无法确定要找的纸牌是不是在其中。

但是查词典时，我们并不是从头到尾、一个词一个词的查。因为单词是以字母顺序排列的，所以我们可以使用类似于二分查找的算法：

  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++最终会出现运行时错误。

还没有评论.