所謂二分法又被稱為折半查找法，
是一種效率較高的查找方法
局限性：必須是在有序的， 即表中結點按關鍵字有序，
不妨假設有序表是遞增有序的。 二分法只適用於順序存儲結構
基本概念我們假設一個區間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,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三種情況。
假設有一個排序的按未知的旋轉軸旋轉的陣列(比如， 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)