PHP ordered list binary search (half search) algorithm sharing

This article mainly introduces the binary search (half search) algorithm of PHP ordered table search, briefly introduces the concept and principle of the binary search method, and analyzes the ordered linear table search in PHP based on the binary search algorithm in the form of examples. Friends who need it can refer to the relevant operating skills. I hope it can help everyone.

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;

Run 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.

Related recommendations:

Example analysis of the binary search algorithm implemented in PHP

How to implement the binary search algorithm in PHP

php Recursive and non-recursive binary search example code

The above is the detailed content of PHP ordered list binary search (half search) algorithm sharing. For more information, please follow other related articles on the PHP Chinese website!