PHP binary search algorithm example [recursive and non-recursive methods]

The example in this article describes the PHP binary search algorithm. Share it with everyone for your reference. The details are as follows:

binarySearch

The method used in binary search is relatively easy to understand. Take an array as an example:

① First take the value in the middle of the array floor((low+top)/2),

② Then compare it with the number you want to find. If it is larger than the middle value, replace the first value with the position next to the middle position and continue the operation of the first step; if it is smaller than the middle value, replace the last value with the middle value. Position the previous position, continue the first step

③ Repeat the second step until the target number is found

For example, find the number 23 from 1, 3, 9, 23, 54,

The first position is 0, and the last position is 4, the middle position is 2. The value is 9, which is smaller than 23, then the first position is updated to 2+1, which is 3; then the middle position is (3+4)/2=3, and the value is 23, which is relatively equal. That is to find

//  非递归算法：
//  $target是要查找的目标 $arr是已经排序好的数组
function binary(&$arr,$low,$top,$target){
    while($low <= $top){
//由于php取商是有小数的，所以向下取整，不过也可不加，数组也会取整
      $mid = floor(($low+$top)/2);
      echo $mid."
";
      if($arr[$mid]==$target){
        return $arr[$mid];
      }elseif($arr[$mid]<$target){
        $low = $mid+1;
      }else{
        $top = $mid-1;
      }
    }
    return -1;
}

//  递归算法：
function binaryRecursive(&$arr,$low,$top,$target){
    if($low<=$top){
      $mid = floor(($low+$top)/2);
      if($mid==$target){
        return $arr[$mid];
      }elseif($arr[$mid]<$target){
        return binaryRecursive($arr,$mid+1,$top,$target);
      }else{
        return binaryRecursive($arr,$low,$top-1,$target);
      }
    }else{
      return -1;
    }
}

I hope this article will be helpful to everyone in PHP programming.

For more PHP binary search algorithm examples [recursive and non-recursive methods] related articles, please pay attention to the PHP Chinese website!