二分查找算法（ 递归&&非递归）java

一、二分查找概念：

所谓二分查找就是在一个有序的数组中要查找一个元素（target），首先将target与数组中间元素（mid）比较，如果相等，皆大欢喜；如果target>mid，说明target位于中间元素之后（因为大前提数组是有序的），即target在区间 [mid+1，end]；如果target<mid，target在区间[0，mid-1]，不断缩小查找范围，直到查找到target或查找完所有区间未找到为止，举例如下图：

二分查找.jpg

二、二分查找算法易错点

一定要注意边界条件，否则看似简单的代码很容易写出一手死循环！！！想看看花式犯错集锦？？请戳这位老哥的文章：https://segmentfault.com/a/1190000011283470

三、二分查找算法java实现（递归、非递归）

终于要上代码了：

// 递归
public static boolean binarySearch(int[]arr, int n, int start, int end) {
        if(end <start) return false; //递归结束条件
        int mid = start + (end-start)/2; //避免start,end很大时(start+end)/2溢出
        if(arr[mid]==n) return true;
        else if(n<arr[mid]) return bs(arr,n,start,mid-1);
        else  return bs(arr,n,mid+1,end);
    }

//迭代
public static boolean binarySearch(int[]arr,int n,int start,int end) {
    while(start<=end) {
        int mid = start + (end-start)/2;
        if(arr[mid]==n) return true;
        else if(arr[mid]>n) end = mid-1;
        else start = mid + 1;
    }
    return false;
}