Programmation en général - Algorithmes de recherche binaire

Question

Étant donné un tableau $ array de N nombres et une clé $ key, écrivez l'algorithme de recherche binaire en anglais courant. Si $ array contient $ key, retourne l'index de la clé $; sinon, renvoyez -1.

Quelqu'un peut-il me montrer comment faire?

Answer 1

Ne semble pas que je devrais vous donner le code ici, mais peut-être que cette description peut aider?

1. Trier la liste.

2. Laissez i = length/2

3. Comparer terme à l'index i à votre clé.

   a. S'ils sont égaux, renvoyez l'index.

   b. Si la clé est supérieure à ce terme, répétez 3 (recurse) sur la moitié supérieure de la liste i = (i + length)/2 (ou (i + top)/2 selon la façon dont vous l'implémentez)

   c. Si la clé est inférieure à ce terme, répéter 3 sur la moitié inférieure i = i/2 ou (i + bottom)/2

récursion Stop si/quand le nouveau i est le même que l'ancien i. Cela signifie que vous avez épuisé la recherche. Retour -1

---

Faites attention pour les erreurs hors par un, ce qui peut vous faire exclure certains termes par erreur, ou provoquer une récursion infinie, mais cela est l'idée générale. Assez simple. Pensez-y comme jouant «Devinez le nombre» pour les numéros 1 à 100. Vous prenez une estimation, je vous dis plus haut ou plus bas. Vous dites 50, je dis plus bas. Vous dites 25, je dis plus haut. Vous dites 37 ...

Answer 2

Je sais que c'est peu :) tard, mais prenez anyway.This montrent aussi que la fonction récursive fonctionne plus vite que in_array()

function binarySearch($A,$value,$starting,$ending) 
    { 
     if($ending<$starting) 
     { 
      return -1; 
     } 
     $mid=intVal(($starting+$ending)/2); 

     if($value===$A[$mid]) 
      { 
       return $mid; 
      } 
     else if($value<$A[$mid]) 
      { 
      $ending=$mid-1; 
      } 
     else if($value>$A[$mid]) 
      { 
      $starting=$mid+1; 
      } 

     return binarySearch($A,$value,$starting,$ending); 
    } 

    for($i;$i<1000000;$i++){ 
     $arr[$i]=$i; 
    } 
    $value =99999; 

    $msc=microtime(true); 
    $pos = in_array($value,$arr); 
    $msc=microtime(true)-$msc; 

    echo "Time taken for in_array() : ".round($msc*1000,3).' ms <br>'; 
    if($pos>0) 
    echo $value .' found.'; 
    else 
    echo $value .' not found'; 

    echo "<br><br>"; 
    $msc=microtime(true); 
    $pos = binarySearch($arr,$value ,0,1000000); 
    $msc=microtime(true)-$msc; 

    echo "Time taken for recursive function : ".round($msc*1000,3).' ms<br>'; 
    if($pos>=0) 
    echo $value .' found.'; 
    else 
    echo $value .' not found'; 

Ouput:

Time taken for in_array() : 5.165 ms 
99999 found. 

Time taken for recursive function : 0.121 ms 
99999 found.