@(算法集)
二分查找算法
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法柠新。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列栖袋。
最近在一次聊天中被提問到二分查找算法竟然一下想不起來，巨尷尬抚太，印象中幾款經(jīng)典的算法案例是有學(xué)過的塘幅，回去翻了一下大學(xué)的算法書本，只能怪當(dāng)初沒有好好學(xué)習(xí)... 因此打算開個【算法集】的欄目尿贫，來記錄重新學(xué)習(xí)一些經(jīng)典算法电媳，進一步提高算法能力。
反思一下這兩三年的工作庆亡，主要還是偏架構(gòu)匆背、偏應(yīng)用方向，一些理論上的知識沒有重視身冀，應(yīng)該調(diào)整一下钝尸，需要知其然也要知其所以然括享。
今天先從二分查找算法學(xué)起
首先講個??，如果某一科目成績分?jǐn)?shù)范圍：[0,100]珍促，張三知道自己的成績铃辖，他讓你猜他的成績，如果猜的分?jǐn)?shù)高了或者低了都會告訴你猪叙，用最少的次數(shù)猜出他的成績娇斩，你會如何設(shè)定方案？【排除靠亂猜運氣等等啥的特殊情況】
其實這個也有“粗調(diào)”穴翩、“精調(diào)”的思維模式
- 最笨的方案犬第，從0-100 一直往上猜，這樣運氣最好的情況下是第一次就猜中芒帕，運氣最差100次后才能猜中歉嗓。
-
最優(yōu)的方案，需要引入“粗調(diào)”的思維背蟆，我們可以把數(shù)據(jù)區(qū)間一分為二鉴分，思路也很簡單先猜50，這樣就[0-100]带膀，就分成了[0-49]志珍，[51-100]兩個區(qū)間，等張三反饋答案是：“偏高""垛叨、"偏低"伦糯、"正確"，最好的情況下是50一猜就中嗽元。
如果偏高的話則往[0-49]的區(qū)間繼續(xù)切半猜舔株，反之則往[51-100]的區(qū)間繼續(xù)切半猜，這樣可以保證在最優(yōu)的情況下猜到答案
PHP代碼實現(xiàn)
<?php
function binarySearch($x,$data){
$lower = 0;
$high = count($data)-1;
while($lower <= $high){
$middle = intval(($lower + $high) / 2);
if($data[$middle] > $x){
$high = $middle - 1;
} elseif($data[$middle] < $x){
$lower = $middle + 1;
} else{
return $middle;
}
}
return -1;
}
$data = array(1,2,3,4,5,6,7,8,9);
echo binarySearch(7,$data);
我們來分析一下二分查找算法的優(yōu)缺點：
優(yōu)點：比較次數(shù)少还棱，查找速度快载慈，平均性能好，適用于不經(jīng)常變動而查找頻繁的有序列表
缺點：要求待查表為有序表珍手，換言之办铡，插入數(shù)據(jù)的時候就不能隨便插入了，必須要找到合適的位置才能進行插入
