|
|
Posted on 2011-03-15 12:12 ytl 閱讀(2637) 評論(5) 編輯 收藏 所屬分類: 學習總結 、 Java基礎
關于二分查找的原理互聯網上相關的文章很多，我就不重復了，但網絡的文章大部分講述的二分查找都是其中的核心部分，是不完備的和效率其實還可以提高，如取中間索引使用開始索引加上末尾索引的和除以2，這種做法在數字的長度超過整型的范圍的時候就會拋出異常，下面是我的代碼，其中可能有些地方沒考慮到或有什么不足，希望大家指出，我虛心接受。 
1
public class Sort {
2 private int binarySort(int[] array, int begin, int end, int value, int call) {
3 // 顯示每次調用過程和查找所用的的次數(call)
4 System.out.print(begin + "\t" + end + "\t" + call + "\n");
5 // 如果每次數組的第一個數或最后一個數等于查找的相等直接返回
6 if (array[begin] == value)
7 return begin;
8 if (array[end] == value)
9 return end;
10 // 如果查詢的數字不在數組里面，直接返回-1，從而提高效率
11 if (array[begin] > value)
12 return -1;
13 if (array[end] < value)
14 return -1;
15 // 如果查詢數組只有兩個數那可以直接通過判斷第一個或最后一個是否是查詢值
16 if ((end - begin) < 2) {
17 if (array[begin] == value)
18 return begin;
19 if (array[end] == value)
20 return end;
21 }
22
24 // 下面 mid=(int) (begin + (end - begin) / 2) 可以防止數字長度大于整型數的長度導致異常
26 int mid = (int) (begin + (end - begin) / 2);
27 // 下面是通用的二分查找算法
28 if (array[mid] == value)
29 return mid;
30 if (array[mid] > value) {
31 return binarySort(array, begin, mid - 1, value, call + 1);
32 }
33 return binarySort(array, mid + 1, end, value, call + 1);
34
35 }
36
37 public int sort(int[] array, int value) {
39 return binarySort(array, 0, array.length - 1, value, 1);
40 }
41 }
下面是測試結果：
1 int[] array = { 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 12, 13,
2 14, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 23, 24, 25, 26, 26,
3 27, 28, 29 };
1,System.out.println(sort(array, 1));
0 34 1
0
2,System.out.println(sort(array, 29))
0 34 1
34
3,System.out.println(sort(array, 6))
0 34 1
0 16 2
0 7 3
4 7 4
6 7 5
6
4,System.out.println(sort(array, 28))
0 34 1
18 34 2
27 34 3
31 34 4
33 34 5
33
5,System.out.println(sort(array, -11))
0 34 1
-1
6,System.out.println(sort(array, 100))
0 34 1
-1
7,System.out.println(sort(array, 7))
0 34 1
0 16 2
8（如果有重復的返回的索引是最后一個）、
評論
# re: 二分查找的優化和完備 回復 更多評論
2011-03-15 12:26 by
還不錯，值得學習
# re: 二分查找的優化和完備 回復 更多評論
2011-03-20 10:40 by
mid比end小吧，end是int型，mid怎么會溢出呢
# re: 二分查找的優化和完備 回復 更多評論
2011-03-24 16:22 by
沒必要用遞歸吧，還可以優化，展開成循環。
# re: 二分查找的優化和完備 回復 更多評論
2011-04-20 14:25 by
@嚕嚕
怎么不會溢出呢，heihei,
假設數組的長度剛好是int取值的最大值，
查找的值大于mid 那么下次的折半的mid = （mid+1+last)
（mid+1+last)大于int 范圍吧。
# re: 二分查找的優化和完備[未登錄] 回復 更多評論
2011-08-17 00:33 by
mid = (l+r) / 2
畢竟2分查找還是比較追求速度的，而且r>2^31的情況基本不會出現，因為沒有那么大一個數組。
另外，貌似這個是binarySearch,不是"Sort"吧
|