PHP实战中知识总结 / 排序算法 - 二分查找算法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。其实，二分查找也还是比较容易理解的，大概就是一分为二，然后两边比较，保留有效区间，继续一分为二查找，直到找到或者超出区间则结束。

1、满足该算法的要求必须如下两点

（1）必须采用顺序存储结构。

（2）必须按关键字大小有序排列。

2、算法步骤

（1）确定要查找的区间

（2）确定要二分时的参照点

（3）区间内选取二分点

（4）根据二分点的值，综合左右区间情况以及求解的目的，舍去一半无用的区间

（5） 继续在有效区间重复上面的步骤

/**
* 二分查找算法
* 第一种实现方式：循环方式
* @param int $number
* @param array $arr
* @return int
*/
function binary_search($number,$arr){
  if(!in_array($number,$arr) || empty($number)){
    return -1;
  }
  $length = count($arr);
  $lower = 0;
  $higher = $length-1;
  while ($lower <= $higher){
    $middle = intval(($lower + $higher)/2);
    if($arr[$middle] > $number){ // 以中间点作为参照点比较，查找数比参照点小，舍去右边，否则舍弃左边区间
      $higher = $middle - 1;
    }elseif ($arr[$middle] < $number){
      $lower = $middle +1;
    }else{
      return $middle;
    }
  }
  return -1;
}
// 待查找区间
$arr = [1, 3, 7, 9, 11, 57, 63, 99];
// 非递归查找57所在的位置
$find_key = binary_search($arr, 57);
print_r($find_key);
/**
* 二分查找算法
* 第二种实现方式：递归
* @param array $arr
* @param int $number
* @param int $lower
* @param int $higher
* @return int
*/
function binary_search_recursion($arr,$number,$lower,$higher){
  if($lower > $higher){
    return -1;
  }
  $middle = intval(($lower+$higher) /2);
  if($number > $arr[$middle]){
    // 查找数比参照点大，舍去左边继续查找
    return binary_search_recursion($arr,$number,$middle+1,$higher);
  }elseif ($number < $arr[$middle]){
    return binary_search_recursion($arr,$number,$lower,$middle-1);
  }else{
    return $middle;
  }
}
$arr = [1, 3, 7, 9, 11, 57, 63, 99];
$key = binary_search_recursion($arr,11,0,count($arr));
print_r($key);die;