二分查找也称为折半查找，是对有序元素查找的一种算法，在查找的过程中，不断的将搜索长度减半，因此效率不错。Java 的 JDK 提供了二分法查找的算法，使用的方法是Arrays.binarySearch()。binarySearch() 方法提供了多种数据类型的二分查找，比如实现了int、float、double、char、byte 和 Object 类型，还提供了对泛型的支持。在 JavaAPI 手册中提供了接口说明，比如如下方法：
staticintbinarySearch(long[] a, intfromIndex, inttoIndex, longkey) staticintbinarySearch(long[] a, longkey) staticintbinarySearch(Object[] a, intfromIndex, inttoIndex, Objectkey) staticintbinarySearch(Object[] a, Objectkey) staticintbinarySearch(short[] a, intfromIndex, inttoIndex, shortkey) staticintbinarySearch(short[] a, shortkey) static<T>intbinarySearch(T[] a, intfromIndex, inttoIndex, Tkey, Comparator<?superT>c) static<T>intbinarySearch(T[] a, Tkey, Comparator<?superT>c)
以上是 Arrays 类中提供的部分关于 binanrySearch() 方法的定义，对于不同类型来说，基本提供了两种方法，第一种方法需要在调用时提供数组、开始下标、结束下标和查找的值，比如：
staticintbinarySearch(long[] a, intfromIndex, inttoIndex, longkey)
另外一种查找的方法是提供数组和查找的值即可，比如：
staticintbinarySearch(long[] a, longkey)
对于这两种搜索方法，在 Java 中提供了统一的调用方法，可以查看其代码，在 Java 的安装目录下找到 src.zip 文件，该文件是 Java 的部分源码。将 src.zip 文件解压缩，在java/util/Arrays.java 中可以找到以上两个方法的实现，代码如下：
publicstaticintbinarySearch(long[] a, longkey) { returnbinarySearch0(a, 0, a.length, key); } publicstaticintbinarySearch(long[] a, intfromIndex, inttoIndex, longkey) { rangeCheck(a.length, fromIndex, toIndex); returnbinarySearch0(a, fromIndex, toIndex, key); }
从代码中可以看到，两个方法最后都调用了 binarySearch0() 方法，但是在第二个binarySearch() 方法中调用了 rangeCheck() 方法，该方法用于检查数组长度、开始下标和结束下标的正确性，rangeCheck() 方法的实现如下：
/*** Checks that {@code fromIndex} and {@code toIndex} are in* the range and throws an exception if they aren't.*/privatestaticvoidrangeCheck(intarrayLength, intfromIndex, inttoIndex) { if (fromIndex>toIndex) { thrownewIllegalArgumentException( "fromIndex("+fromIndex+") > toIndex("+toIndex+")"); } if (fromIndex<0) { thrownewArrayIndexOutOfBoundsException(fromIndex); } if (toIndex>arrayLength) { thrownewArrayIndexOutOfBoundsException(toIndex); } }
如果调用第一个 binarySearch() 方法，数组长度、开始下标和结束下标是方法中自行获取的，因此不需要进行 rangeCheck()，而调用第二个 binarySearch() 方法时，数组长度、开始下标和结束下标是调用时外部提供的，因此为了保证正确性进行了 rangeCheck()。
二分法真正的实现是 binarySearch0() 方法，根据不同的数据类型，binarySearch0() 方法也提供了多种重载，这里只看 long 类型的实现，代码如下：
privatestaticintbinarySearch0(long[] a, intfromIndex, inttoIndex, longkey) { intlow=fromIndex; inthigh=toIndex-1; while (low<=high) { intmid= (low+high) >>>1; longmidVal=a[mid]; if (midVal<key) low=mid+1; elseif (midVal>key) high=mid-1; elsereturnmid; // key found } return-(low+1); // key not found.}
二分查找的思路是从有序（从小到大）数组的中间位置开始查找，如果中间位置的数小于查找的目标值，则查找数组中间值右侧的部分，如果中间位置的数大于查找的目标值，则查找数组中间值左侧的部分，如果相等，则返回当前的下标，如果没有找到则返回一个负数。
除了上面的实现外，还有一种针对泛型的 binarySeach() 的方法，如下：
static<T>intbinarySearch(T[] a, intfromIndex, inttoIndex, Tkey, Comparator<?superT>c) static<T>intbinarySearch(T[] a, Tkey, Comparator<?superT>c)
在上面两个方法的定义中，最后一个参数是一个比较器，比较器的作用是比较两个元素的大小用的，查看以上两个方法的实现，代码如下：
publicstatic<T>intbinarySearch(T[] a, Tkey, Comparator<?superT>c) { returnbinarySearch0(a, 0, a.length, key, c); } publicstatic<T>intbinarySearch(T[] a, intfromIndex, inttoIndex, Tkey, Comparator<?superT>c) { rangeCheck(a.length, fromIndex, toIndex); returnbinarySearch0(a, fromIndex, toIndex, key, c); }
以上两个方法同样调用了 binarySearch0() 方法，该 binarySearch0() 方法的实现代码如下：
privatestatic<T>intbinarySearch0(T[] a, intfromIndex, inttoIndex, Tkey, Comparator<?superT>c) { if (c==null) { returnbinarySearch0(a, fromIndex, toIndex, key); } intlow=fromIndex; inthigh=toIndex-1; while (low<=high) { intmid= (low+high) >>>1; TmidVal=a[mid]; intcmp=c.compare(midVal, key); if (cmp<0) low=mid+1; elseif (cmp>0) high=mid-1; elsereturnmid; // key found } return-(low+1); // key not found.}
观察代码的第 12 行，c 是比较器，该比较器中提供了一个 compare() 方法用来比较两个元素的大小，如果 midVal 比 key 小，compare 返回负数，如果 midVal 比 key 大，compare 返回整数，如果 midVal 和 key 相等，compare 则返回 0。
以上就是在学习 Arrays 工具类的使用时，顺便简单的阅读了它的实现，而刚好又能看懂，所以记录在此！
