[TOC] # 二分法查詢指定數組中是否包含指定成員 原理是先將數組有序排列，比如升序。 然后不停的取數組中位數與指定值比較，按比較的大小結果，如果恰好相等則存在。 否則在中位數以上或以下的剩下半個數組中繼續獲取中位數進行比較。已達到每一次查詢都可以縮小剩下查詢范圍的一半。 ## 循環實現 ``` $arr = array(2,33,22,1,323,321,28,36,90,123); //二分法查找 $index = binarySearch($arr,321); var_dump($index); function binarySearch($arr,$key){ sort($arr); $len = count($arr); $start = 0; $end = $len-1; while($start<=$end){ $mid = (int)(($start+$end)/2); //echo $mid."\n"; if($arr[$mid] == $key){ return $mid; }else if($key > $arr[$mid]){ $start = $mid+1; }else if($key < $arr[$mid]){ $end = $mid-1; } } return -1; } ``` ## 遞歸實現 ``` //search函數 其中$array為數組，$k為要找的值，$low為查找范圍的最小鍵值，$high為查找范圍的最大鍵值 function search($array, $k, $low=0, $high=0) { if(count($array)!=0 and $high == 0) //判斷是否為第一次調用 { $high = count($array); } if($low <= $high) //如果還存在剩余的數組元素 { $mid = intval(($low+$high)/2); //取$low和$high的中間值 if ($array[$mid] == $k) //如果找到則返回 { return $mid; } elseif ($k < $array[$mid]) //如果沒有找到，則繼續查找 { return search($array, $k, $low, $mid-1); } else { return search($array, $k, $mid+1, $high); } } return -1; } $array = array(4,5,7,8,9,10); //測試search函數 echo search($array, 8); //調用search函數并輸出查找結果 ```