Saturn's Weblog

二分法查找（Binary Search）是一种搜索算法（平均的时间复杂度为O(log n)），支持对一个有序列表中的某个元素进行快速查找。更多二分法查找的解释和例子可以参考维基百科的说明。

这里我只写出其在PHP中的算法实现，仅作记录。如果你有更好的实现方法，请在下方留言与我交流。

//script by Saturn from cnsaturn.com

function binarySearch($searchArray, $targetValue)
{
    //初始范围为全部数组
    $startIndex = 0;
    $endIndex = count($searchArray) - 1;
    //初始中间位置的元素索引
    $middle = round(($endIndex - $startIndex) / 2);
 
    //如果要搜索的元素在初始开始位置，则直接返回
    if($targetValue == $searchArray[$startIndex])
    {
       return $startIndex;
     }
 
    //如果要搜索的元素在初始结束位置，则直接返回
    if($targetValue == $searchArray[$endIndex])
    {
       return $endIndex;
    }
 
    //循环查找
    while($searchArray[$middle] !== $targetValue && $startIndex < $endIndex)
    {
       //调整搜索起止范围
       if($searchArray[$middle] > $targetValue)
       {
          $endIndex = $middle;
       }
       else if($searchArray[$middle] < $targetValue)
       {
          $startIndex = $middle;
       }
  
      //调整中间位置元素的索引，注意获得索引值的方法
      $middle = round(($endIndex - $startIndex) /2) + $startIndex;   
   }
 
   //返回目标值的索引，如果未找到则返回-1
   return ($searchArray[$middle] == $targetValue) ? $middle : -1;
}

创建一个数组和一个目标值来测试上述查找算法：

$array = array(1,2,3,4,5,6,7,8);

//echo 4;
echo binarySearch($array, 5);