DAA - Recherche binaire

Dans ce chapitre, nous discuterons d'un autre algorithme basé sur la méthode de division et de conquête.

Énoncé du problème

La recherche binaire peut être effectuée sur un tableau trié. Dans cette approche, l'index d'un élémentxest déterminé si l'élément appartient à la liste des éléments. Si le tableau n'est pas trié, une recherche linéaire est utilisée pour déterminer la position.

Solution

Dans cet algorithme, nous voulons savoir si l'élément x appartient à un ensemble de nombres stockés dans un tableau numbers[]. Oùl et r représentent les index gauche et droit d'un sous-tableau dans lequel l'opération de recherche doit être effectuée.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Une analyse

La recherche linéaire s'exécute dans O(n)temps. Alors que la recherche binaire produit le résultat dansO(log n) temps

Laisser T(n) être le nombre de comparaisons dans le pire des cas dans un tableau de n éléments.

Par conséquent,

$$ T (n) = \ begin {cases} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & sinon \ end {cases} $$

En utilisant cette relation de récurrence $ T (n) = log \: n $.

Par conséquent, la recherche binaire utilise $ O (log \: n) $ time.

Exemple

Dans cet exemple, nous allons rechercher l'élément 63.