一、二分查找概念：
所謂二分查找就是在一個(gè)有序的數(shù)組中要查找一個(gè)元素（target）宽涌，首先將target與數(shù)組中間元素（mid）比較褐鸥，如果相等似芝，皆大歡喜那婉；如果target>mid，說明target位于中間元素之后（因?yàn)榇笄疤釘?shù)組是有序的）党瓮，即target在區(qū)間 [mid+1详炬，end]；如果target<mid寞奸，target在區(qū)間[0呛谜，mid-1]，不斷縮小查找范圍蝇闭，直到查找到target或查找完所有區(qū)間未找到為止呻率，舉例如下圖：
二分查找.jpg
二硬毕、二分查找算法易錯(cuò)點(diǎn)
一定要注意邊界條件呻引，否則看似簡(jiǎn)單的代碼很容易寫出一手死循環(huán)Ｇ诶骸？肯埂！想看看花式犯錯(cuò)集錦蚯窥？韭脊？請(qǐng)戳這位老哥的文章：https://segmentfault.com/a/1190000011283470
三童谒、二分查找算法java實(shí)現(xiàn)（遞歸、非遞歸）
終于要上代碼了：
// 遞歸
public static boolean binarySearch(int[]arr, int n, int start, int end) {
if(end <start) return false; //遞歸結(jié)束條件
int mid = start + (end-start)/2; //避免start,end很大時(shí)(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;
}
