|
|
Posted on 2011-03-15 12:12 ytl 閱讀(2639) 評(píng)論(5) 編輯 收藏 所屬分類: 學(xué)習(xí)總結(jié) 、 Java基礎(chǔ)
關(guān)于二分查找的原理互聯(lián)網(wǎng)上相關(guān)的文章很多，我就不重復(fù)了，但網(wǎng)絡(luò)的文章大部分講述的二分查找都是其中的核心部分，是不完備的和效率其實(shí)還可以提高，如取中間索引使用開始索引加上末尾索引的和除以2，這種做法在數(shù)字的長度超過整型的范圍的時(shí)候就會(huì)拋出異常，下面是我的代碼，其中可能有些地方?jīng)]考慮到或有什么不足，希望大家指出，我虛心接受。 
1
public class Sort {
2 private int binarySort(int[] array, int begin, int end, int value, int call) {
3 // 顯示每次調(diào)用過程和查找所用的的次數(shù)(call)
4 System.out.print(begin + "\t" + end + "\t" + call + "\n");
5 // 如果每次數(shù)組的第一個(gè)數(shù)或最后一個(gè)數(shù)等于查找的相等直接返回
6 if (array[begin] == value)
7 return begin;
8 if (array[end] == value)
9 return end;
10 // 如果查詢的數(shù)字不在數(shù)組里面，直接返回-1，從而提高效率
11 if (array[begin] > value)
12 return -1;
13 if (array[end] < value)
14 return -1;
15 // 如果查詢數(shù)組只有兩個(gè)數(shù)那可以直接通過判斷第一個(gè)或最后一個(gè)是否是查詢值
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) 可以防止數(shù)字長度大于整型數(shù)的長度導(dǎo)致異常
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 }
下面是測(cè)試結(jié)果：
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（如果有重復(fù)的返回的索引是最后一個(gè)）、
評(píng)論
mid比end小吧，end是int型，mid怎么會(huì)溢出呢
沒必要用遞歸吧，還可以優(yōu)化，展開成循環(huán)。
@嚕嚕
怎么不會(huì)溢出呢，heihei,
假設(shè)數(shù)組的長度剛好是int取值的最大值，
查找的值大于mid 那么下次的折半的mid = （mid+1+last)
（mid+1+last)大于int 范圍吧。
mid = (l+r) / 2
畢竟2分查找還是比較追求速度的，而且r>2^31的情況基本不會(huì)出現(xiàn)，因?yàn)闆]有那么大一個(gè)數(shù)組。
另外，貌似這個(gè)是binarySearch,不是"Sort"吧
|