# 二分查找 ## 現實中的例子： > 我們日常生活中，很多人應該有這種經歷，朋友、同學或者同事淘了個寶貝，神秘兮兮的過來讓大家猜多少錢，在約定一個價格范圍之后（比如10-100），大家會七嘴八舌的猜起價格來： > > 「50」 「高了」 > > 「30」 「低了」 > > 「40」 「高了」 > > 「36」 「對了」 > > 如果我們用順序遍歷的邏輯，最差需要91次，才能猜到價格，現實生活中，沒人會這么干，我們采用上面這種邏輯，只需要4次就猜到價格了，快了幾十倍，而且數據量越大，優勢越明顯。 ## 定義： > 針對的是`一個有序的數據集合`（這點很重要），查找思想有點類似分治思想。每次都通過跟區間的中間元素對比，將待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間被縮小為 0。注意到二分查找針對的必須是已經排序過的有序數組，否則不能使用該算法。  ## 代碼： ~~~ /** * 二分查找 * @param $nums * @return mixed */ function binary_search($nums,$num){//傳入數組和需要查找的數據 return binary_search_internal($nums,$num,0,count($nums)-1); } function binary_search_internal($nums,$num,$low,$high){ if($low>$high){ return -1;//沒有找到，即數組中不存在這個值 } $mid = floor(($low+$high)/2); if($num>$nums[$mid]){ return binary_search_internal($nums,$num,$mid+1,$high); }elseif($num<$nums[$mid]){ return binary_search_internal($nums,$num,$low,$mid-1); }else{ return $mid; } } $nums = [1,2,3,4,5,6]; $index = binary_search($nums,5); print $index; ~~~ ## 總結： 1. 時間復雜度：O(logn) 2. 二分查找在線性表結構中的應用非常廣泛 3. 針對有序數組 4. 二分查找適用于變動不是很頻繁的靜態序列集，如果序列集變動很頻繁，經常進行插入刪除操作，那么就要不斷維護這個序列集的排序，這個成本也很高，因此，這種情況下就不適用二分查找了，比如我們的數據庫查詢，增刪改查很頻繁，顯然不是通過二分查找來進行查詢的，后面我們會討論，如何針對動態變化的序列集進行查詢操作。