Example of PHP Ordered Table Lookup Two part Lookup (Half part Lookup) Algorithm

  • 2021-09-11 19:48:07
  • OfStack

In this paper, an example is given to describe the two-point search (half-point search) algorithm of PHP ordered table search. Share it for your reference, as follows:

Introduction:

2-point search technology, also known as half-fold search. Its premise is that the records in the linear table must be key ordered (usually from small to ordered), and the linear table must be stored sequentially.

Basic ideas:

In the ordered table, the intermediate record is taken as the comparison object, and if the given value is equal to the keyword of the intermediate record, the search is successful; If the given value is less than the keyword of the intermediate record, the search is continued in the left half of the intermediate record; If the given value is greater than the key of the intermediate record, the search continues in the right half of the intermediate record. Repeat the above process until the search is successful, or all the search areas have no records and the search fails.

Code:


<?php
//2 Sub-search ( Fold half search ) Algorithm ( The premise is that the array must be an ordered array )  The time complexity is  O(logn)
$i = 0; // Number of times to store comparisons 
//@param  Array to be found 
//@param  Numbers to be searched 
function binsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; // Counter 
  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;
  }
 }
 // Return -1 Indicates that the lookup failed 
 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 results:


7
3

Summary:

The time complexity of the 2-fork lookup is O (logn). However, because the precondition of 2-fork lookup is to store ordered tables sequentially (arrays), if the ordered tables need to perform insertion or deletion operations frequently, maintaining ordered sorting will bring a lot of workload.

More readers interested in PHP can check the topics of this site: "PHP Data Structure and Algorithm Tutorial", "php Programming Algorithm Summary", "php String (string) Usage Summary", "PHP Array (Array) Operation Skills Complete Book", "PHP Common Traversal Algorithms and Skills Summary" and "PHP Mathematical Operation Skills Summary"

I hope this article is helpful to everyone's PHP programming.


Related articles: