加载中...

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


还没有评论.