java 核心技术 v1 9.6.3 二分查找
9.6.3 Binary Search / 二分查找
为了找到数组中的一个对象，你可能要访问所有元素，直到遇到一个匹配。
1. 排序后列表的二分查找
但如果数组排过序，你可以直接查看中间的元素，检查该元素是否比你想要的元素大:
如果是，就查找数组的前半部分；
否则，查看后半部分；
这样就把问题拆解了一半，之后继续按照这种方式查找。
比如一个数组数组有 1024 个元素，你将会在 10 步之后找到匹配（或确认没有该元素)，而相比一个线性查找，在元素存在的情况下，平均花费 512 步才能找到，此外，要花费 1024 步才能确认元素不存在。
Collections 类 binarySearch 实现了上面的算法。注意集合必须排过序，不然算法会给出的错误答案。
2. 二分查找的使用方法
为完成一个元素的查找，只需提供集合（实现了 List 接口 —— 见下面的小贴士）和要定位的元素。如果集合中的元素，还未排序，可以通过 Comparable 接口 compareTo ，提供 a comparator 对象。
i = Collections.binarySearch(c, element);
i = Collections.binarySearch(c, element, comparator);2. 二分查找返回值的使用
一个非负的返回值，表示匹配对象的索引。
这就是说, c.get(i) 就等于在比较后的 element 的次序；
一个负值，说明没有匹配的元素，但你可以利用这个值，计算你可以将 element 插入集合的位置，使得集合仍保持排序状态，插入的位置为
insertionPoint = -i - 1;
结果没有设定为更简单的 -i ，是因为这样 0 值就会造成不确定。
总之，下面操作会把元素加入到正确的位置：
if (i < 0)
c.add(-i -1, element);重要的一点是，二分查找需要随机访问。如果你不得不一个个迭代到一个链表的中间元素，你会丧失了二分查找的全部优势。因此，如果你提供的是链表，binarySearch 会恢复到线程方式执行查找。
附 java.util.Collections 1.2