二分查找的递归实现和非递归实现

二分查找的递归实现和非递归实现【java】

（1）非递归实现二分查找。
算法是由静态方法binarySearch()实现的,它接受一个整数健和一个有序的int数组作为参数。如果该健存在于数组中，则返回他的索引，否则返回-1。
算法使用两个变量lo和hi，并保证如果健在数组中则它一定在a[lo…hi]中，然后方法进入一个循环，不断地将数组的中间健（索引为mid）和被查找的健比较。如果被查找的健等于a[mid]，返回mid；否则算法将查找的范围缩小一半，如果被查找的健小于a[mid]就继续在左边查找，如果被查找的健大于a[mid]就继续在右边查找。
算法找到被查找的健，或者是查找范围为空时，该过程结束。
二分查找的时间复杂度O(logn)。
以下为二分查找的详细代码。

import java.util.*;//导入必要的包。
public class BinarySearch2{
	public static int binarySearch(int[] a,int key){
		int lo=0;//指向数组的第一个元素。
		int hi=a.length-1;//指向数组的最后一个元素。
		while(lo<=hi){
			int mid=(lo+hi)/2;//取数组中间。
			if(key>a[mid])  lo=mid+1;//将key与左右比较。
			else if(key<mid) hi=mid-1;
			else return mid; //找到。
			}
		return -1;//当lo>hi时表示未找到。
		}
	public static void main(String[] agrs){//主函数
		int[] a={1,22,3,112,6,7,9,126,78,93,12,48};
		Scanner scanner=new Scanner(System.in);
		Arrays.sort(a);//二分查找首先要对数组排序。
		System.out.print("请输入要查找的关键字：");
		int key=scanner.nextInt();
		if(binarySearch(a,key)<0){
			System.out.println(key+"不在数组内");
			}
		else System.out.println(key+"在数组内");
		} 
	}

运行结果：

（2）递归实现二分查找
用递归的方法实现二分查找，去掉上面代码种的循环，重复的调用函数binarySearch()。
递归出口：lo>hi查找失败时，或者key=a[mid]查找成功时。
由于没有了循环不能实时的改变mid的值，故要完成递归需要在函数binarySearch()中引入两个参数lo和hi。
时间复杂度O(logn)。

import java.util.*;//导入必要的包。
public class BinarySearch3{
	public static int binarySearch(int[] a,int key,int lo,int hi){
		int mid=(lo+hi)/2;//数组中间位置。
		if(lo>hi) return -1;//递归出口。
		if(key<a[mid]) return binarySearch(a,key,lo,mid-1);//key的值与a[mid]比较，依次递归。
		else if(key>a[mid]) return binarySearch(a,key,mid+1,hi);
		else return mid;//找到。
		} 
	
	public static void main(String[] args){
		int[] a={112,34,4,533,765,212,74,6,90,100};
		Arrays.sort(a);//二分查找的前提条件是有序数组。
		Scanner scanner=new Scanner(System.in);
		System.out.print("请输入您要查找的关键字：");
		int key=scanner.nextInt();
		if(binarySearch(a,key,0,a.length-1)<0){
			System.out.println(key+"不在数组中");
			}
		else{
			System.out.println(key+"在数组中");
						}
		
		}
	
	}

运行结果：

本人编程小白若有错误或不足之处，欢迎指正。