一、二分查找概念：
所谓二分查找就是在一个有序的数组中要查找一个元素（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;
}
