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

小鱼儿 2022-07-16 10:49 198阅读 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;
        }

![这里写图片描述][20161016231912864]

![这里写图片描述][20161016231933098]

[20161016231912864]: /images/20220716/fb346d8f1bd6480bb8343e66e08bf012.png
[20161016231933098]: /images/20220716/7f6db4115ea3448ba1502e37d3827d8c.png