二分查找（递归实现+非递归实现）

二分查找，又称折半查找（Binary Search），是一种效率较高的查找方法。二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

步骤描述：

1. 首先确定整个查找区间最中间位置mid=start+(end-start)/2;
2. 将处于表中间位置的关键字arr[mid]与所需查找的关键字key进行比较；
3. 若key=arr[mid]，则查找成功；若key<arr[mid]，则在前（左）半个区域继续进行二分查找；若key>arr[mid]，则在后（右）半个区域继续进行二分查找；
4. 重复上述过程，直到查找成功。

二分查找递归实现：

Java实现（使用递归）：

public static int BinarySearch(int[] arr,int target,int start,int end){
        if(target<arr[start]||target>arr[end]||start>end){
            return -1;
        }
        //mid=(start+end)/2有可能溢出
        int mid=start+(end-start)/2;
        if(arr[mid]>target){
            return BinarySearch(arr,target,start,mid-1);
        }else if(arr[mid]<target){
            return BinarySearch(arr,target,mid+1,end);
        }else{
            return mid;
        }
    }

测试代码：

 public static void main(String[] args){
        int[] arr={2,4,6,8,12,16,19,22,25,26,29,30,36,39,47,58,66,71,77,88};
        int target=39;
        System.out.println(BinarySearch(arr,target,0,arr.length-1));
    }

二分查找非递归实现：

Java实现（不使用递归）：

public static int BinarySearch(int[] arr,int target) {
	int start=0;
	int end=arr.length-1;
	int middle=0;
	if(target<arr[start]||target>arr[end]||start>end) {
		return -1;
	}
	while(start<=end) {
		//middle=(start+end)/2有可能溢出
		middle=start+(end-start)/2;
		if(target<arr[middle]) {
			end=middle-1;
		}
		else if(target>arr[middle]) {
			start=middle+1;
		}
		else {
			return middle;	
		}
	}
	return -1;
}

测试代码：

public static void main(String[] args) {
	int[] arr= {2,4,6,8,12,16,19,22,25,26,29,30,36,39,47,58,66,71,77,88};
	int target=39;
	System.out.print(BinarySearch(arr,target));
}