PHP trouve si un tableau ordonné contient une certaine valeur (recherche binaire)

Question : Pour un tableau ordonné, comment déterminer si une valeur donnée existe dans le tableau.

Idée : Pour déterminer s'il existe, le moyen le plus simple est de parcourir directement le tableau et de comparer chaque valeur. Mais pour les tableaux ordonnés, une telle écriture ne parvient absolument pas à tirer parti de la fonctionnalité "ordonnée".

Tout ce que nous utilisons "recherche binaire",

//有序数组为
$arr = array(2,5,66,87,954,1452,5865);
//查找值
$str = 1452;
//我们先定义 三个参数
$front = 0;//一个开始值下标
$end = count($arr) - 1;//一个结束值下标
$mid = intval(($front + $end) / 2);//中间值下标

1 Pour la première comparaison, nous jugeons directement si la valeur de recherche str est égale à la valeur intermédiaire mid, et si elle est égale, il renvoie vrai directement ;

2. Si la valeur de recherche str est supérieure à la valeur médiane mid, cela signifie que la valeur de recherche str peut être du côté droit de la valeur médiane, c'est-à-dire la valeur de départ. front doit être réaffecté = la valeur médiane mid + 1, et la valeur finale end n'a pas besoin de changer, et la valeur médiane est séquentiellement La valeur mid est la nouvelle valeur de début + la valeur de fin

3. Si la valeur de recherche str est inférieure à la valeur médiane mid, cela signifie que la valeur de recherche str peut être à gauche de la valeur médiane, c'est-à-dire que la valeur de début n'a pas besoin de changer et la valeur de fin end doit être réaffectée. = valeur moyenne - 1, et la valeur médiane mid est la valeur de début + la nouvelle valeur de fin

-----Comme ci-dessus, comparez la valeur de début, la valeur de fin et la valeur moyenne entrantes ; Une fois que la valeur de début est supérieure à la valeur de fin, cela signifie qu'elle n'est pas trouvée et la requête se termine. Sinon, elle renvoie qu'elle a été trouvée.

Le code spécifique est le suivant :

$str = 89;//查找值
$arr = [1,55,66,89,420];//有序数组
$ren = find($arr, $str);
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
var_dump($ren);
function find($arr, $str){
    $front = 0;//开始下标
    $end = count($arr) - 1;//结束下标
    while($front <= $end){//结束值 大于 开始值 ，反之则退出
        $mid = intval(($front + $end) / 2);//中间值下标
        if($str == $arr[$mid]){
            return $mid;//存在直接返回值的下标
        }
        if($str > $arr[$mid]){
            $front = $mid + 1;//在前面
        }
        if($str < $arr[$mid]){
            $end = $mid - 1;//在后面
        }
    }
    return false;
}

Résultat renvoyé : 89 est l'indice de valeur du quatrième élément 3

Tutoriel vidéo recommandé : "Tutoriel php"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!