PHP ordered list search----Binary search (half)

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 equal to the key of the middle record, the search is successful; if the given value is less than the middle record If the given value is greater than the keyword of the middle record, the search will continue in the left half of the middle record. If the given value is greater than the keyword of the middle record, the search will continue 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;

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.

The above is the content of PHP ordered table search--binary search (halved). For more related content, please pay attention to the PHP Chinese website (www.php.cn)!