什麼是二分法？
所謂二分法又被稱為折半查找法，是一種效率較高的查找方法
侷限性：必須是在有序的，即表中結點按關鍵字有序，並且要用向量作為表的存儲結構。
不妨假設有序表是遞增有序的。二分法只適用於順序存儲結構
基本概念
我們假設一個區間R[low......high]為一個順序遞增的區間
計算中心點mid=(low+high)/2
將要查找的值與R[mid].key的值進行比較，如果大於此值則可知此數肯定是大宇[low...mid]的區間的，於是在[mid...high]此區間取下一個中心值也就是(mid+high)/2，依次類推
總結：每經過一次與當前查找區間的中點位置上的結點關鍵字的比較，就可確定查找是否成功，不成功則當前的查找區間就縮小一半。這一過程重複直至找到關鍵字為K的結點，或者直至當前的查找區間為空(即查找失敗)時為止。
遞歸還是while
這時候我們通常回去選擇某種方法去調用它，我們是選擇遞歸還是while循環呢，各有什麼優劣呢
遞歸的優點：編寫代碼速度快，較為清晰
遞歸的缺點：
效率上來看：1.遞歸由於是函數調用自身，而函數調用是有時間和空間的消耗的：每一次函數調用，都需要在內存棧中分配空間以保存參數、返回地址以及臨時變量，而往棧中壓入數據和彈出數據都需要時間。
2.遞歸中很多計算都是重複的，由於其本質是把一個問題分解成兩個或者多個小問題，多個小問題存在相互重疊的部分，則存在重複計算，如fibonacci斐波那契數列的遞歸實現。
從性能上來看：調用棧可能會溢出，其實每一次函數調用會在內存棧中分配空間，而每個進程的棧的容量是有限的，當調用的層次太多時，就會超出棧的容量，從而導致棧溢出。
而在正式的工程中都是儘量要避免遞歸的
而我們的while呢相對來說就比遞歸性能、效率好得多，但是有個最大的問題就是容易死循環
下面一個簡單的例子演示一下基本的二分法
典型面試題 1
給定一個排序數組和一個目標值，如果在數組中找到目標值則返回索引。如果沒有，返回到它將會被按順序插入的位置。
你可以假設在數組中無重複元素。
例如：
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
首先按照二分法的方式進行查找，在這裡如果查找不到我們不再返回一個“查找不到”的反饋了，而是去判斷要插入得到位置，插入的位置很明顯是在start、end 或者end+1三種情況。根據情況再做相應的if條件即可
會了這道題才敢說自己真的會了二分法
假設有一個排序的按未知的旋轉軸旋轉的數組(比如，0 1 2 4 5 6 7 可能成為4 5 6 7 0 1 2)。給定一個目標值進行搜索，如果在數組中找到目標值返回數組中的索引位置，否則返回-1。
你可以假設數組中不存在重複的元素。
例如：
給出[4， 5，6，7,，1， 2， 3]和target=1，返回 2
給出[4， 5，6，7,，1， 2， 3和target=0，返回 -1
分析：
分析此數組，不管怎麼組合結果都是兩個遞增的數組(4,5,6,7)(1,2,3) 還是(3,4,5,6,7)(1,2)
閱讀更多 全棧佈道者 的文章
