Detailed explanation of PHP half search algorithm case

This time I will bring you a detailed explanation of the PHP half-search algorithm case. What are the precautions when using PHP half-search. The following is a practical case, let's take a look.

Introduction:

Binary search technology, also known as half search. Its premise is that the records in the linear table must be in key order (usually in order from small to large), and the linear table must be stored sequentially.

Basic idea:

In an ordered list, take the middle record as the comparison object. If the given value is the key of the middle record If equal, the search is successful; if the given value is less than the key of the middle record, the search continues in the left half of the middle record; if the given value is greater than the key of the middle record, the search continues 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.

Code:

<?php
//二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn)
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function binsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //计数器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  $middle = intval(($lower + $high) / 2);
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 //返回-1表示查找失败
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = binsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

Running result:

7
3

Summary:

The time complexity of binary search is O(logn). However, since the prerequisite for binary search is the sequential storage of an ordered table (array), if the ordered table requires frequent insertion or deletion operations, maintaining the ordered sorting will bring a considerable workload.

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

PHP long connection use case analysis

Detailed explanation of PHP application containerization and deployment usage

The above is the detailed content of Detailed explanation of PHP half search algorithm case. For more information, please follow other related articles on the PHP Chinese website!