二分法查找的效率

系统管理员 2021-03-28 14:07 547阅读 0赞

结果:排序需要耗费巨大时间。单纯二分查找需要时间很少，其空间复杂度为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;
        }
    }