How to implement the binary search algorithm in PHP

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

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);
?>

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

Detailed explanation of examples of binary search and half search in java algorithm

javascript half search detailed explanation_javascript skills

javascript Find the position of a character in an array by half (ordered list)_javascript skills

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