|
|
Posted on 2011-03-15 12:12 ytl 阅读(2627) 评论(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"吧
|