首页 > 代码库 > 查找算法

查找算法

2024-07-04 05:07:37   218人阅读

　　　　顺序查找的时间复杂度是O(n)，如果数组一开始是有序的，那么用顺序查找的效率是比较低的，因为二分查找等方式能够拥有更低的时间复杂度，但是如果一开始是无序的，那么顺序查找有可能比其他查找更加的快速。

　　　　二分查找主要是应用在有序的数组织中，采取的是一种分治的思想，先在数组中去中值，然后将中值与查询的值进行比较，如果小，就在左边数组中查询，如果大，就在右边数组中查询，这样就缩小了查询的范围，同时在半个数组中还能进一步进行划分，能够加快查询的速度。

    private static int a[] = {1,2,3,4,5,6,7,8};
    //非递归
     public static void binarySort(int low,int high,int c) {
         int mid =( low+high)/2;
         System.out.println("mid is "+mid+" and a[mid] is "+a[mid]);
         if(c==a[mid]){
             System.out.println("find");
         }else if(c<a[mid]){
             high = mid-1;
             if(low<=high)
             binarySort(low,high,c);
         }else if(c>a[mid]){
             low = mid+1;
             if(low<=high)
             binarySort(low,high,c);
         }
     }
     
     //递归
     public static void binarySorts(int low,int high,int c) {
        while(low<=high){
             int mid =( low+high)/2;
             if(c==a[mid]){
                 System.out.println("find");
                 break;
             }else if(c<a[mid]){
                 high = mid-1;
             }else if(c>a[mid]){
                 low = mid+1;
             }
        }
     }

分别采用递归和非递归的方式进行了实现。


联系
我们