12.8　二分法查找

在字典中查找单词时，你不会从头到尾地逐页查找。由于单词是按字母顺序排列的，因此你很可能用二分法查找（binary search）算法。

(1) 从字典中间附近的某页开始。

(2) 将要查找的单词与该页的某个单词比较。如果找到，则就此结束。

(3) 如果这个单词排在要查找的单词前面，就往后翻并回到第 2 步。

(4) 如果该页的单词排在要查找的单词后面，就往前翻并回到第 2 步。

如果你在某页找到两个相邻的单词，即要查找的单词应排在它们之间，那么你就知道这本字典没有你要找的单词。

对于前面的 Card 对象数组，如果其中的 Card 对象是按顺序排列的，我们就可编写一个速度更快的 search 版本：

  1. public static int binarySearch(Card[] cards, Card target) {
  2.     int low = 0;
  3.     int high = cards.length - 1;
  4.     while (low <= high) {
  5.         int mid = (low + high) / 2;                 // 第1步
  6.         int comp = cards[mid].compareTo(target);
  8.         if (comp == 0) {                            // 第2步
  9.             return mid;
  10.         } else if (comp < 0) {                      // 第3步
  11.             low = mid + 1;
  12.         } else {                                    // 第4步
  13.             high = mid - 1;
  14.         }
  15.     }
  16.     return -1;
  17. }

我们首先声明了变量 low 和 high，用于表示要搜索的范围。一开始，我们搜索整个数组，从 0 到 length - 1。

在 while 循环中，我们重复二分法查找的 4 个步骤：

(1) 选择一个位于 low 和 high 之间的索引（mid），并将该索引处的 Card 对象同目标进行比较。

(2) 如果找到目标，就返回这个索引。

(3) 如果 mid 处的 Card 对象比目标小，就在范围 mid + 1 到 high 中搜索。

(4) 如果 mid 处的 Card 对象比目标大，就在范围 low 到 mid - 1 中搜索。

如果 low 大于 high，那么就意味着这个范围内没有任何 Card 对象，因此退出循环并返回-1。注意，这个算法依赖于对象的方法 compareTo。