本文實例為大家分享了Java實現二分查找的變種，供大家參考，具體內容如下
普通二分查找：
先回顧一下普通的二分查找
注意：二分查找有這樣一個問題：當數組中數有重復時，比如 ｛3，3，3，3｝ 這個數組，二分查找3時，返回的是arr[1]，也就是說二分查找并不會返回3第一次出現的位置0。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
public class BinarySearch { public static <T extends Comparable<? super T>> int search(T arr[], T value) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = (left & right) + ((left ^ right) >> 1); if (arr[mid].compareTo(value) == 0) { return mid; } else if (arr[mid].compareTo(value) > 0) { right = mid - 1; } else { left = mid + 1; } } return -1; } public static void main(String[] args) { Integer[] arr = new Integer[]{1, 3, 3, 6, 7, 9}; //-1 System.out.println(search(arr, 0)); //0 System.out.println(search(arr, 1)); //5 System.out.println(search(arr, 9)); //-1 System.out.println(search(arr, 10)); //2 System.out.println(search(arr, 3)); }} |
二分變種：findFirst函數
在普通二分查找中，在[left....right]左閉右閉區間中查找，如果找到了值為value的元素就認為找到了。而在這個findFirst函數中就不是如此，在[left....right]左閉右閉區間中查找，當找到值等于value的元素后，不是讓right = mid - 1，而是讓right = mid，繼續在[left....right]左閉右閉區間中查找。最終left== right時就退出循環。
退出循環后可能找到了value值，也有可能是循環遍歷完整個數組后都沒找到value，而退出循環。
所以退出循環后還要在判斷一下是那種情況。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
public class BinarySearch { public static <T extends Comparable<? super T>> int findFirst(T arr[], T value) { int left = 0; int right = arr.length - 1; //當left>=right時退出，這里的“=”情況與二分不同 while (left < right) { int mid = (left + right) >> 1; if (arr[mid].compareTo(value) < 0) { left = mid + 1; } else { right = mid; } } // 上面循環遍歷完后。是找到了value值？還是沒找到value值？判斷一下。 if (arr[left] == value) { return left; } else { return -1; } } public static void main(String[] args) { Integer[] arr = new Integer[]{1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9}; //-1 System.out.println(findFirst(arr, 0)); //0 System.out.println(findFirst(arr, 1)); //12 System.out.println(findFirst(arr, 9)); //-1 System.out.println(findFirst(arr, 10)); //1 System.out.println(findFirst(arr, 3)); }} |
二分變種：fewer函數
介紹
給定一個數組，和一個變量value,從數組中找出值最接近value值而且比value小的那個數。比如 arr = {11，22，22，33 ，33，33，44，54} value = 33。 22最接近value，而且比value小。
所以答案是2 ( 22在數組arr中的下角標 ) 。
如果沒找到比value小的數，那么輸出 -1。
解決思路
用二分查找方法。每次用 arr[mid] 來與value進行比對。小、等于，去左邊找；大，去右邊找。可能上一句的“等于”的情況你不太理解。普通二分查找是找出arr[mid] == value，而fewer函數是為了找出比value小的數，所以盡管arr[mid] == value，還得繼續去左邊找更小的值。
例子
代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class BinarySearch { public static <T extends Comparable<? super T>> int fewer(T arr[], T value) { int left = 0; int right = arr.length - 1; //當left > right 時退出 while (left <= right) { int mid = (left & right) + ((left ^ right) >> 1); if (value.compareTo(arr[mid]) <= 0) { right = mid - 1; } else { left = mid + 1; } } return right; } public static void main(String[] args) { Integer[] arrF = new Integer[]{21, 23, 25, 25, 31, 34, 37, 39, 52, 63}; //3 System.out.println(fewer(arrF, 30)); }} |
二分變種：greater函數
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://www.cnblogs.com/noKing/p/8016713.html
