Example explanation of the binary search algorithm implemented in PHP

This article mainly introduces the half-search algorithm implemented in PHP, briefly describes the principle of half-search, and analyzes the related operating skills of PHP using recursive and non-recursive methods to implement the half-search algorithm in the form of examples. Friends who need it can Refer to the following

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

Definition: Half search technology, which is binary search. Its premise is that the records in the linear table must be in key order (usually from large to small), and the linear table must be stored sequentially.

The basic idea of ​​half search: Take the middle record as the comparison object. If the given value is the key of the middle record, then the key of the middle record is equal, then the search is successful; if If the given value is less than the key of the middle record, continue searching; if the given value is greater than the key of the middle record, continue searching in the right half of the middle record. Repeat the above process until the search is successful or there is no record in all search areas and the search fails.

Implementation code:

<?php
//递归方式
function bin_recur_search($arr,$val){
  global $time;
  if(count($arr) >= 1){
    $mid = intval(count($arr) / 2);
    $time++;
    if($arr[$mid] == $val){
      return &#39;值为:&#39;.$arr[$mid].&#39;<br>查找次数：&#39;.$time.&#39;<br>&#39;;
    }elseif($arr[$mid] > $val){
      $arr = array_splice($arr,0,$mid);
      return bin_recur_search($arr, $val);
    }else{
      $arr = array_slice($arr,$mid + 1);
      return bin_recur_search($arr, $val);
    }
  }
  return &#39;未找到&#39;.$val;
}
//非递归方式
function bin_search($arr,$val){
  if(count($arr) >= 1){
    $low = 0;
    $high = count($arr);
    $time = 0;
    while($low <= $high){
      $time++;
      $mid = intval(($low + $high)/2);
      if($val == $arr[$mid]){
        return &#39;索引：&#39;.$mid.&#39;<br>值为：&#39;.$arr[$mid].&#39;<br>查找次数：&#39;.$time;
      }elseif($val > $arr[$mid]){
        $low = $mid + 1;
      }else{
        $high = $mid - 1;
      }
    }
  }
  return &#39;未找到&#39;.$val;
}
$arr = array(1,3,5,7,7,9,25,68,98,145,673,8542);
echo bin_recur_search($arr, 673);
echo bin_search($arr, 673);
?>

Running result:

值为:673
查找次数：4
索引：10
值为：673
查找次数：4

Articles you may be interested in:

Example of string matching algorithm implemented in PHP

Example explanation of the maximum forward matching algorithm implemented in PHP

Installation and use of the PHP performance analysis tool xhprof and related precautions

The above is the detailed content of Example explanation of the binary search algorithm implemented in PHP. For more information, please follow other related articles on the PHP Chinese website!