Recherche de liste ordonnée PHP ---- Recherche binaire (la moitié)

Introduction :

Technologie de recherche binaire, également connue sous le nom de demi-recherche. Son principe est que les enregistrements du tableau linéaire doivent être classés dans l'ordre des clés (généralement du plus petit au plus grand) et que le tableau linéaire doit être stocké de manière séquentielle.

Idée de base :

Dans une liste ordonnée, prenez l'enregistrement du milieu comme objet de comparaison. Si la valeur donnée est égale à la clé de l'enregistrement du milieu, la recherche est réussie ; la valeur donnée est inférieure à l'enregistrement du milieu. Si la valeur donnée est supérieure au mot-clé de l'enregistrement du milieu, la recherche se poursuivra dans la moitié gauche de l'enregistrement du milieu. Si la valeur donnée est supérieure au mot-clé de l'enregistrement du milieu, le la recherche se poursuivra dans la moitié droite de l'enregistrement du milieu. Répétez le processus ci-dessus jusqu'à ce que la recherche réussisse ou qu'il n'y ait aucun enregistrement dans toutes les zones de recherche et que la recherche échoue.

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;

Résumé :

La complexité temporelle de la recherche binaire est O(logn). Cependant, étant donné que la condition préalable à la recherche binaire est le stockage séquentiel d'une table ordonnée (tableau), si la table ordonnée nécessite des opérations d'insertion ou de suppression fréquentes, le maintien du tri ordonné entraînera une charge de travail considérable.

Ce qui précède est le contenu de la recherche de table ordonnée PHP - recherche binaire (réduit de moitié). Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !