基本概念：
二分查找也叫做折半查找，利用了元素間的次序關係，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務，是一種效率較高的查找方法。
應用場景：
1.必須採用順序存儲結構。
2.必須按關鍵字大小有序排列。
查找過程：
首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
時間複雜度：
二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x
時間複雜度無非就是while循環的次數！
總共有n個元素，
漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩餘個數），其中k就是循環的次數
由於你n/2^k取整後>=1
即令n/2^k=1
可得k=log2n,（是以2為底，n的對數）
所以時間複雜度可以表示O(h)=O(log2n)
下面貼出遞歸和非遞歸兩種實現方式的代碼：
相信會有不少小夥伴也是會這麼寫吧，正常運行其實也不會出現什麼問題。
但是，仔細分析程序會發現其中確實存在一個很有名的“溢出漏洞”。
注意12行,beginIndex+endIndex如果超過2的31次方時，就會導致溢出！
那麼如何溢出的呢？
不妨假設有這麼一個數組，數組長度為為2^31-1（有符號的32位整數的最大值）。數組元素從1一直到2^31-1遞增排列。假設target（待查找的元素）是2^31-2（倒數第二個元素）。
初始數組
第一次循環：
第一次循環的中間值
第一次循環數組情況
第一次循環後發現2^31-2是在數組的右半部分，於是
開始索引右移一位
此時右半部分成為我們查找的目標數組：
右半部分數組
下一次循環，計算中間值為：
此時mid總和超過2^31，結果導致溢出。這將導致不可預知的結果。
這就是二分查找中那個知名的“溢出漏洞”。20多年來這個漏洞一直未被發現，直到2006年上報sun公司後得以修補。
這是來自維基百科的說明：
修補的方法：
-
int midIndex = beginIndex+(endIndex - beginIndex) / 2 ; 替換方案1
int midIndex = beginIndex+(endIndex - beginIndex) >>1 ; 替換方案2
int midIndex=(beginIndex+endIndex)>>1;// 替換方案3
閱讀更多 碼農的搬磚生涯 的文章
