二分法binarySearch探究与改进 - 黑马程序员技术交流社区

import java.util.Arrays;
public class ArraysDemo2 {
* 需求：编程实现二分法查找并改进
*
* @author Aaron
* @verson 2015-11-19 14:07:17
*/
public static void main(String[] args) {
// int[] arr = {23,4,4,12,21,44,1,99,34};//小数据
int[] arr = new int[200000];//大量数据
for(int i=0; i<arr.length; i=i+2){
arr[i] = i;
arr[i+1] = i;
}
//选择排序，对小数据先排个序
xuanZe(arr);
// System.out.println(Arrays.toString(arr));
//普通二分法查找元素，若没找到，返回该数字插入数组时排序位置的负数减1
int index = myBinarySearch(arr,4);
System.out.println(index);
//二分法改进，能返回重复元素的角标数组，如果没有，返回数字插入数组时排序索引的负数减
long start = System.currentTimeMillis();
int[] superIndex = superBinarySearch(arr,130);
for(int index1 : superIndex)
System.out.print(index1+" ");
long end = System.currentTimeMillis();
System.out.println("改进的二分法用时"+(end-start)+"毫秒！");
//遍历数组方法获取某元素所在角标集合，如果没有，返回只含-1元素的数组
long start1 = System.currentTimeMillis();
int[] index2;
index2 = indexSearch(arr,130);
for(int index1 : index2)
System.out.print(index1+" ");
long end1 = System.currentTimeMillis();
System.out.println("遍历数组方法用时"+(end1-start1)+"毫秒！");
}
//遍历数组
private static int[] indexSearch(int[] arr, int num) {
int[] index = new int[arr.length];
Arrays.fill(index, -1);
int pos = 0;
for(int i=0; i<arr.length; i++){
if(arr[i]==num)
index[pos++] = i;
}
if(pos==0)
return Arrays.copyOf(index, 1);
return Arrays.copyOf(index,pos);
}
//改进二分法
private static int[] superBinarySearch(int[] arr, int num) {
int start = 0;
int end = arr.length-1;
int mid;
int[] index = new int[arr.length];
Arrays.fill(index, -1);
int pos = 0;//角标数组的指针位置，存一次加一次，最后按位置截取
while(start<=end){
if(arr[start]==num){
index[pos++] = start;
while(arr[++start]==num)
index[pos++] = start;
return Arrays.copyOf(index, pos);
}
if(arr[end]==num){
index[pos++] = end;
while(arr[--end]==num)
index[pos++] = end;
return Arrays.copyOf(index, pos);
}
mid = (start+end)/2;
if(arr[mid]>num)
end = mid-1;
else if(arr[mid]<num)
start = mid+1;
else if(arr[mid]==num){
int midback = mid-1;
while(arr[midback--]==num)
index[pos++] = midback;
index[pos++] = mid;
while(arr[++mid]==num)
index[pos++] = mid;
return Arrays.copyOf(index, pos);
}
}
index[pos++] = -start-1;
return Arrays.copyOf(index, pos);
}
//一般二分法
private static int myBinarySearch(int[] arr,int num) {
int start = 0;
int end = arr.length-1;
int mid;
while(start<=end){
if(arr[start]==num)
return start;
if(arr[end]==num)
return end;
mid = (start+end)/2;
if(arr[mid]>num){
end = mid-1;
}else if(arr[mid]<num){
start = mid+1;
}else return mid;
}
return -start-1;
}
//选择排序
private static void xuanZe(int[] arr) {
int temp;
for (int i = 0; i < arr.length-1; i++) { //循环次数
for (int j = i; j < arr.length; j++) { //每次大循环从前往后确定一个最小值
if(arr[i]>arr[j]){
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}

复制代码