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

水深无声 2022-05-29 06:17 261阅读 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);}
    	}
    }