用二分法在一个数组中查找数组元素

时间:2022-04-30 22:12:29

二分法的使用数组必须是有序的,或升序,或降序

$array  = [1,2,3,4,5,6,7,8,9];

function search_element($array, $value, $start, $end)
{
  // 开始位置不能小于结束位置
  if($start > $end) return -1;

  // 获取中间位置
  $index = intval(($start + $end) / 2);

  // 判断在哪个区间, 递归
  if($value < $array[$index]) {
    return search_element($array, $value, $start, $index - 1);
  } elseif($value > $array[$index]) {
    return search_element($array, $value,  $index + 1, $end);
  } else {
    return $index;
  }
}

echo bsearch_r(1, $arr, 0, count($arr)-1);// 0
echo bsearch_r(14, $arr, 0, count($arr)-1);// -1