二分查找的递归与非递归

二分查找介绍：
二分查找是分治策略应用最简单的实例，分治策略是将规模较大的问题分解成同类型规模较小的问题。二分查找是针对有序的序列查询，它可以有效降低时间复杂度。我们知道对有序或无序的序列查询，需要对该序列进行遍历，时间复杂度为O(n)，而二分查找每次使数据量缩减一半，一直继续下去，所以二分查找的时间复杂度是O(log₂n)。

二分查找过程：

算法实现：

//非递归循环实现
public static int BinarySearch(int[] a,int val){
    int pos = -1;
    int left = 0,right = a.length-1;
    while(left<=right){
        int mid = (right-left+1)/2+left;
        if(val<a[mid]){
            right = mid-1;
        }else if(val>a[mid]){
            left = mid+1;
        }else {
            pos = mid;
            break;
        }
    }
    return pos;
}
//递归实现
public static int BinarySearch(int[] a,int val,int i,int j){
    if(i>j || val<a[i] || val>a[j]){
        return -1;
    }else{
        int mid = (i+j)/2;
        if(a[mid]>val){
            return BinarySearch(a,val,i,mid-1);
        } else if(a[mid]<val){
            return BinarySearch(a,val,mid+1,j);
        }else{
            return mid;
        }
    }
}