[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函数并输出查找结果 ```