结果:排序需要耗费巨大时间。单纯二分查找需要时间很少，其空间复杂度为O(1)，时间复杂度为O(logN),而普通查找的时间复杂度为O(N)，空间复杂度也为O(1)。
测试数据使用python代码生成，
#coding=utf-8
import random;
fp=open("test.txt","w+");
n=50000000;
k=50000000;
for i in range(1,n):
r=random.randint(1,k);
fp.write(str(r)+"\n");
fp.close();
测试java代码如下，
public class Demo {
public static void main(String[] args) {
String dstFile = args[0];
// System.out.println(dstFile);
int[] a = readInts("test.txt");
int[] b = readInts("search.txt");
long start = System.currentTimeMillis();
// for(int i=0;i<b.length;i++){
// if(find(a,b[i])){
// System.out.println(b[i] + " find!");
// }
// }
long s1=System.currentTimeMillis();
Arrays.sort(a); // 排序时间比较多，查找时间是相当短地，经过测试对于5千万的数据，
long s2=System.currentTimeMillis();
System.out.println("the sort cost time is " + (s2-s1)/1000.0 + "s");
long ss=System.currentTimeMillis();
for(int i=0;i<b.length;i++){
if(binaryQuery(a,b[i]) != -1){
System.out.println(b[i] + " find!");
}
}
long ee=System.currentTimeMillis();
System.out.println("the binary find cost time is " + (ee-ss)/1000.0 + "s");
long end = System.currentTimeMillis();
System.out.println("the cost time is " + (end-start)/1000.0 + "s");
// List<int[]> list = Arrays.asList(a);
// System.out.println(list.);
// File f = new File();
// FileInputStream
}
private static int[] readInts(String path){
File f = new File(path);
List<Integer> list = new ArrayList<Integer>();
BufferedReader br = null;
try {
br = new BufferedReader(new FileReader(f));
String temp = null;
while((temp = br.readLine()) != null){
int k = Integer.valueOf(temp);
// System.out.println(temp);
list.add(k);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
if(br != null){
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
br = null;
}
}
// String[] array = (String[])list.toArray(new String[list.size()]);
// int[] ret = new int[list.size() - 1];
// for(int i=0;i<array.length - 1;i++){
// ret[i] = Integer.valueOf(array[i]);
// }
Integer[] tempRet = list.toArray(new Integer[list.size()]);
int[] ret = new int[list.size()];
for(int i=0;i<tempRet.length;i++){
ret[i] = tempRet[i];
}
return ret;
}
private static boolean find(int[] a,int x){
int k = rawQuery(a, x);
if(k == -1){
return false;
}
return true;
}
private static int rawQuery(int[] a,int x){
for(int i=0;i<a.length;i++){
if(x==a[i]){
return i;
}
}
return -1;
}
private static int binaryQuery(int[] a,int x){
int l=0,h=a.length-1;
while(l <= h){
int mid = (l+h)/2;
if(x < a[mid]){
h = mid - 1;
} else if(x > a[mid]){
l = mid + 1;
} else{
return mid;
}
}
return -1;
}
}
转载于:https://www.cnblogs.com/likeshu/p/6896405.html
