Detailed explanation of PHP half search algorithm case-PHP Tutorial-php.cn

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

Introduction:

Binary searchtechnology, 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:

 $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 "
"; echo $i;

Copy after login

Running result:

7 3

Copy after login

Summary:

The time complexity of binary search isO(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!