一头扎进算法导论-二分法查找-蒲公英云

一头扎进算法导论-二分法查找

小鱼儿 2022-07-16 10:49 245阅读 0赞

定义：分治算法的另一种体现。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半，递归找，即可。

步骤：
（1）确定该区间的中间位置 mid
（2）将查找的值 value 与 a[mid] 比较。
若相等，查找成功返回此位置；
否则确定新的查找区域，继续二分查找。
区域确定如下：
value < a[mid] : 新区域为a[start] 至 s[mid-1]
value > a[mid] : 新区域为a[mid+1] 至 s[end]

临界条件： start<=end

时间复杂度:O(log2n)

代码实现：

//根据归并算法，写一个迭代，递归的二分法查找，算法复杂度为log2(n)
    public int searchByRecursion(int[] a,int start,int end,int value){
        if(end<start){
   //临界条件,等于是可以的，临界的数
            return  -1;
        }else{
            int mid = (start+end)/2;//求取中间值，奇数为中间值，偶数为中间两个值小的那一个
            if(value>a[mid]){
   //如果值比中间的值大，那么，开始的坐标移动成为中间值右边的一个数
                start = mid+1;
                return searchByRecursion(a, start, end, value);
            }else if(value<a[mid]){
   //如果值比中间的值小，那么，开始的坐标移动成为中间值左边的一个数
                end = mid-1;
                return searchByRecursion(a, start, end, value);
            }else{
                return mid;//返回坐标
            }
        }
    }
    //非递归模式
    public int searchByErgodic(int[] a,int start,int end,int value){    
        while(end>=start){
   //等于号是可取的，表示临界状态
            int mid = (start+end)/2;
            if(value==a[mid]){
                return mid;
            }else if(value>a[mid]){
                start=mid +1;
            }else if(value<a[mid]){
                end = mid -1;
            }
        }
        return -1;
    }