二分查找（非递归算法和递归算法）-蒲公英云

二分查找（非递归算法和递归算法）

水深无声 2022-05-29 06:17 342阅读 0赞

非递归算法：
package mytest;
public class test {
    public static int BinarySearch(int low,int high,int[]arr,int x){
        int loc=-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(x==arr[mid]){loc=mid;break;}
            else if(x<arr[mid])
                {high=mid-1;}
            else {low=mid+1;}
        }
        return loc;
    }
    public static void main(String[]args){
        int[]myArr={1,2,3,4,5,6};
        int loc=-1;
        loc=BinarySearch(0,myArr.length-1,myArr,15);
        if(loc==-1){System.out.println("Not found");}
        else{System.out.println("Find it!location is："+loc);}
    }
}
递归算法：
package mytest;
public class test {
    public static int BinarySearch(int low,int high,int[]arr,int x,int loc){
        if((low<=high)&&(loc==-1)){
                int mid=(low+high)/2;
                if(x==arr[mid]){loc=mid;return loc;}
                else if(x<arr[mid])
                    {high=mid-1;}
                else {low=mid+1;}
                loc=BinarySearch(low,high,arr,x,loc);
        }
        return loc;
    }
    public static void main(String[]args){
        int[]myArr={1,2,3,4,5,6};
        int loc=-1;
        loc=BinarySearch(0,myArr.length-1,myArr,5,loc);
        if(loc==-1){System.out.println("Not found");}
        else{System.out.println("Find it!location is："+loc);}
    }
}

总结：

(1)非递归算法中，用的是while,break循环。循环停止的条件是区间为0 ，或者是在区间不为0时已找到该数。

(2)递归算法中，用的是if(){}return语句，满足If条件时，{先缩小区间，然后调用递归}，if语句需要判断的是当区间不为0且仍没有找到数时，才继续缩小区间和调用递归。(注意两个条件关系是&&而不是||，因为如果是||的话，即使查找区间缩小为0了，当没有找到数时，内部会继续更新Low和high的值，造成比较数的时候数组下标溢出)

(3)二分查找时，原数组必须是有序数组

二分查找法是对一组有序的数字中进行查找，传递相应的数据，进行比较查找到与原数据相同的数据，查找到了返回对应的数组下标，没有找到返回-1；

改进：

用上述我自己编写的递归算法不太直观，容易出错。

《算法第4版—谢璐云》中提到，编写递归代码时要注意以下三点：

（1）递归总有一个最简单的情况—方法的第一条语句总是包含最简单的return条件语句（if(不满足递归调用的条件)return）

（2）递归调用总是尝试去解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。

（3）递归调用的父问题和尝试解决的子问题之间不应该有交集。

改进的递归算法：

package mytest;
public class test {
    public static int BinarySearch(int low,int high,int[]arr,int x){
        if(low>high) return -1;
        int mid=(low+high)/2;
        if(x<arr[mid]) return BinarySearch(low,mid-1,arr,x);
        else if (x>arr[mid]) return BinarySearch(mid+1,high,arr,x);
        else return mid;
    }
    public static void main(String[]args){
        int[]myArr={1,2,3,4,5,6};
        int loc=-1;
        loc=BinarySearch(0,myArr.length-1,myArr,5);
        if(loc==-1){System.out.println("Not found");}
        else{System.out.println("Find it!location is："+loc);}
    }
}

去除多余中间变量的非递归算法：

package mytest;
public class test {
    public static int BinarySearch(int low,int high,int[]arr,int x){
        while(low<=high){
            int mid=(low+high)/2;
            if(x==arr[mid]) {return mid;}
            else if(x<arr[mid])
                {high=mid-1;}
            else {low=mid+1;}
        }
        return -1;
    }
    public static void main(String[]args){
        int[]myArr={1,2,3,4,5,6};
        int loc=BinarySearch(0,myArr.length-1,myArr,6);
        if(loc==-1){System.out.println("Not found");}
        else{System.out.println("Find it!location is："+loc);}
    }
}