Arrays的二分查找

　　二分查找也稱為折半查找，是對有序元素查找的一種演算法，在查找的過程中，不斷的將搜索長度減半，因此效率不錯。Java的JDK提供了二分法查找的演算法，使用的方法是Arrays.binarySearch()。binarySearch()方法提供了多種數據類型的二分查找，比如實現了int、float、double、char、byte和Object類型，還提供了對泛型的支持。在JavaAPI手冊中提供了介面說明，比如如下方法：

1 static int binarySearch(long[] a, int fromIndex, int toIndex, long key)
2 static int binarySearch(long[] a, long key)
3 static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
4 static int binarySearch(Object[] a, Object key)
5 static int binarySearch(short[] a, int fromIndex, int toIndex, short key)
6 static int binarySearch(short[] a, short key)
7 static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
8 static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

　　以上是Arrays類中提供的部分關於binanrySearch()方法的定義，對於不同類型來說，基本提供了兩種方法，第一種方法需要在調用時提供數組、開始下標、結束下標和查找的值，比如：

static int binarySearch(long[] a, int fromIndex, int toIndex, long key)

　　另外一種查找的方法是提供數組和查找的值即可，比如：

static int binarySearch(long[] a, long key)

　　對於這兩種搜索方法，在Java中提供了統一的調用方法，可以查看其代碼，在Java的安裝目錄下找到src.zip文件，該文件是Java的部分源碼。將src.zip文件解壓縮，在java/util/Arrays.java中可以找到以上兩個方法的實現，代碼如下：

1 public static int binarySearch(long[] a, long key) {
2     return binarySearch0(a, 0, a.length, key);
3 }
4 
5 public static int binarySearch(long[] a, int fromIndex, int toIndex,
6                                long key) {
7     rangeCheck(a.length, fromIndex, toIndex);
8     return binarySearch0(a, fromIndex, toIndex, key);
9 }

　　從代碼中可以看到，兩個方法最後都調用了binarySearch0()方法，但是在第二個binarySearch()方法中調用了rangeCheck()方法，該方法用於檢查數組長度、開始下標和結束下標的正確性，rangeCheck()方法的實現如下：

 1 /**
 2  * Checks that {@code fromIndex} and {@code toIndex} are in
 3  * the range and throws an exception if they aren't.
 4  */
 5 private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
 6     if (fromIndex > toIndex) {
 7         throw new IllegalArgumentException(
 8                 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
 9     }
10     if (fromIndex < 0) {
11         throw new ArrayIndexOutOfBoundsException(fromIndex);
12     }
13     if (toIndex > arrayLength) {
14         throw new ArrayIndexOutOfBoundsException(toIndex);
15     }
16 }

　　如果調用第一個binarySearch()方法，數組長度、開始下標和結束下標是方法中自行獲取的，因此不需要進行rangeCheck()，而調用第二個binarySearch()方法時，數組長度、開始下標和結束下標是調用時外部提供的，因此為了保證正確性進行了rangeCheck()。

　　二分法真正的實現是binarySearch0()方法，根據不同的數據類型，binarySearch0()方法也提供了多種重載，這裡只看long類型的實現，代碼如下：

 1 private static int binarySearch0(long[] a, int fromIndex, int toIndex,
 2                                  long key) {
 3     int low = fromIndex;
 4     int high = toIndex - 1;
 5 
 6     while (low <= high) {
 7         int mid = (low + high) >>> 1;
 8         long midVal = a[mid];
 9 
10         if (midVal < key)
11             low = mid + 1;
12         else if (midVal > key)
13             high = mid - 1;
14         else
15             return mid; // key found
16     }
17     return -(low + 1);  // key not found.
18 }

　　二分查找的思路是從有序（從小到大）數組的中間位置開始查找，如果中間位置的數小於查找的目標值，則查找數組中間值右側的部分，如果中間位置的數大於查找的目標值，則查找數組中間值左側的部分，如果相等，則返回當前的下標，如果沒有找到則返回一個負數。

　　除了上面的實現外，還有一種針對泛型的binarySeach()的方法，如下：

1 static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
2 static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

　　在上面兩個方法的定義中，最後一個參數是一個比較器，比較器的作用是比較兩個元素的大小用的，查看以上兩個方法的實現，代碼如下：

1 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
2     return binarySearch0(a, 0, a.length, key, c);
3 }
4 
5 public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
6                                    T key, Comparator<? super T> c) {
7     rangeCheck(a.length, fromIndex, toIndex);
8     return binarySearch0(a, fromIndex, toIndex, key, c);
9 }

　　以上兩個方法同樣調用了binarySearch0()方法，該binarySearch0()方法的實現代碼如下：

 1 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
 2                                      T key, Comparator<? super T> c) {
 3     if (c == null) {
 4         return binarySearch0(a, fromIndex, toIndex, key);
 5     }
 6     int low = fromIndex;
 7     int high = toIndex - 1;
 8 
 9     while (low <= high) {
10         int mid = (low + high) >>> 1;
11         T midVal = a[mid];
12         int cmp = c.compare(midVal, key);
13         if (cmp < 0)
14             low = mid + 1;
15         else if (cmp > 0)
16             high = mid - 1;
17         else
18             return mid; // key found
19     }
20     return -(low + 1);  // key not found.
21 }

　　觀察代碼的第12行，c是比較器，該比較器中提供了一個compare()方法用來比較兩個元素的大小，如果midVal比key小，compare返回負數，如果midVal比key大，compare返回整數，如果midVal和key相等，compare則返回0。

　　以上就是在學習Arrays工具類的使用時，順便閱讀了它的實現，而剛好又能看懂，所以記錄在此！