12.9　跟踪代码

为了搞明白二分法查找的工作原理，在循环开头添加如下打印语句大有帮助：

  1. System.out.println(low + ", " + high);

如果像下面这样调用 binarySearch：

  1. Card card = new Card(11, 0);
  2. System.out.println(binarySearch(cards, card));

且要查找的 Card 对象位于索引 10 处，则输出如下：

  1. 0, 51
  2. 0, 24
  3. 0, 11
  4. 6, 11
  5. 9, 11
  6. 10

如果要查找的 Card 对象（如 new Card(15, 1)，即方块 15）不在数组中，输出将如下：

  1. 0, 51
  2. 26, 51
  3. 26, 37
  4. 26, 30
  5. 26, 27
  6. -1

每执行一次循环，low 和 high 之间的距离都将减半。因此，经过 k 次迭代后，余下的 Card 对象数为 52/2k。要确定多少次迭代后查找才会结束，可求解方程 52/2k=1。结果为 log252，即大约 5.7。因此，可能只需要查看 5 或 6 个 Card 对象，而不需要像顺序查找那样查看全部的 52 个 Card 对象。

推而广之，如果数组包含 n 个元素，则二分法查找需要作 log2n 次比较，而顺序查找需要作 n 次比较。n 很大时，二分法查找的速度要快得多。