相比于笨拙的遍历数组，二分法是对数组中元素查找效率很高的一种方法，但前提是数组本身是有序的，且只能返回一个索引，这样的话，二分法虽然高效却不能对含重复元素的数组的元素索引进行全部获取，也就是说，某个元素在数组中出现2次或两次以上，二分法查找此元素索引只能随机获取其中的一个，这样的话，很不爽~。
下面给出的改进的二分法可以返回该重复元素的所有索引，并且和遍历数组方法进行了性能上的比较，数据量比较小时遍历数组用时较少，因为一方面，改进的二分法逻辑判断较多，另一方面，数据太少二分法体现不出高效；而数据量较大时，改进的二分法速度上明显优于数组遍历！

1. import java.util.Arrays;
   
2. 
   
3. public class ArraysDemo2 {
   
4. 
   
5.         
   
6.          * 需求：编程实现二分法查找并改进
   
7.          *
   
8.          * @author Aaron
   
9.          * @verson 2015-11-19 14:07:17
   
10.          */
    
11.         public static void main(String[] args) {
    
12.                
    
13. //                int[] arr = {23,4,4,12,21,44,1,99,34};//小数据
    
14.                 int[] arr = new int[200000];//大量数据
    
15.                 for(int i=0; i<arr.length; i=i+2){
    
16.                         arr[i] = i;
    
17.                         arr[i+1] = i;
    
18.                 }
    
19. 
    
20.                 //选择排序，对小数据先排个序
    
21.                 xuanZe(arr);
    
22. //                System.out.println(Arrays.toString(arr));
    
23.                
    
24.                 //普通二分法查找元素，若没找到，返回该数字插入数组时排序位置的负数减1
    
25.                 int index = myBinarySearch(arr,4);
    
26.                 System.out.println(index);
    
27.                
    
28.                 //二分法改进，能返回重复元素的角标数组，如果没有，返回数字插入数组时排序索引的负数减
    
29.                 long start = System.currentTimeMillis();
    
30.                 int[] superIndex = superBinarySearch(arr,130);
    
31.                 for(int index1 : superIndex)
    
32.                         System.out.print(index1+" ");
    
33.                 long end = System.currentTimeMillis();
    
34.                 System.out.println("改进的二分法用时"+(end-start)+"毫秒！");
    
35.                
    
36.                 //遍历数组方法获取某元素所在角标集合，如果没有，返回只含-1元素的数组
    
37.                 long start1 = System.currentTimeMillis();
    
38.                 int[] index2;
    
39.                 index2 = indexSearch(arr,130);
    
40.                 for(int index1 : index2)
    
41.                         System.out.print(index1+" ");
    
42.                 long end1 = System.currentTimeMillis();
    
43.                 System.out.println("遍历数组方法用时"+(end1-start1)+"毫秒！");
    
44.         }
    
45.         
    
46. //遍历数组
    
47.         private static int[] indexSearch(int[] arr, int num) {
    
48.                 int[] index = new int[arr.length];
    
49.                 Arrays.fill(index, -1);
    
50.                 int pos = 0;
    
51.                 for(int i=0; i<arr.length; i++){
    
52.                         if(arr[i]==num)
    
53.                                 index[pos++] = i;
    
54.                 }
    
55.                 if(pos==0)
    
56.                         return Arrays.copyOf(index, 1);
    
57.                 return Arrays.copyOf(index,pos);
    
58.         }
    
59. 
    
60. //改进二分法
    
61.         private static int[] superBinarySearch(int[] arr, int num) {
    
62.                 int start = 0;
    
63.                 int end = arr.length-1;
    
64.                 int mid;
    
65.                 int[] index = new int[arr.length];
    
66.                 Arrays.fill(index, -1);
    
67.                 int pos = 0;//角标数组的指针位置，存一次加一次，最后按位置截取
    
68.                
    
69.                 while(start<=end){
    
70.                         if(arr[start]==num){
    
71.                                 index[pos++] = start;
    
72.                                 while(arr[++start]==num)
    
73.                                         index[pos++] = start;
    
74.                                 return Arrays.copyOf(index, pos);
    
75.                         }
    
76.                         if(arr[end]==num){
    
77.                                 index[pos++] = end;
    
78.                                 while(arr[--end]==num)
    
79.                                         index[pos++] = end;
    
80.                                 return Arrays.copyOf(index, pos);
    
81.                         }
    
82.                         mid = (start+end)/2;
    
83.                         if(arr[mid]>num)
    
84.                                 end = mid-1;
    
85.                         else if(arr[mid]<num)
    
86.                                 start = mid+1;
    
87.                         else if(arr[mid]==num){
    
88.                                 int midback = mid-1;
    
89.                                 while(arr[midback--]==num)
    
90.                                         index[pos++] = midback;
    
91.                                 index[pos++] = mid;
    
92.                                 while(arr[++mid]==num)
    
93.                                         index[pos++] = mid;
    
94.                                 return Arrays.copyOf(index, pos);
    
95.                         }
    
96.                 }
    
97.                 index[pos++] = -start-1;
    
98.                 return Arrays.copyOf(index, pos);
    
99.         }
    
100. 
     
101. //一般二分法
     
102.         private static int myBinarySearch(int[] arr,int num) {
     
103.                 int start = 0;
     
104.                 int end = arr.length-1;
     
105.                 int mid;
     
106.                 while(start<=end){
     
107.                         if(arr[start]==num)
     
108.                                 return start;
     
109.                         if(arr[end]==num)
     
110.                                 return end;
     
111.                         mid = (start+end)/2;
     
112.                         if(arr[mid]>num){
     
113.                                 end = mid-1;
     
114.                         }else if(arr[mid]<num){
     
115.                                 start = mid+1;
     
116.                         }else return mid;
     
117.                                 
     
118.                 }
     
119.                 return -start-1;
     
120.         }
     
121. 
     
122. //选择排序
     
123.         private static void xuanZe(int[] arr) {
     
124.                 int temp;
     
125.                 for (int i = 0; i < arr.length-1; i++) { //循环次数
     
126.                         for (int j = i; j < arr.length; j++) { //每次大循环从前往后确定一个最小值
     
127.                                 if(arr[i]>arr[j]){
     
128.                                         temp = arr[i];
     
129.                                         arr[i] = arr[j];
     
130.                                         arr[j] = temp;
     
131.                                 }
     
132.                         }
     
133.                 }
     
134.         }
     
135. }

复制代码

运行结果：
5      ------这是二分法的
131 130 改进的二分法用时5毫秒！
130 131 遍历数组方法用时8毫秒！

是不是快了许多，如果将测试数据130改为-130，数组中并不存在的数据，结果为：
5
-1 改进的二分法用时4毫秒！
-1 遍历数组方法用时8毫秒

怎么没人呐，啊啊啊啊

顶顶顶顶