Recherche linéaire et binaire

Intoduction

In this article, we are going to introduce linear and binary search to Python beginners, Lists are the only data structure concept that should be assimilated in order to keep up with this tutoriel.

Recherche linéaire

Supposons que vous cherchez un roman dans une étagère : une manière de le faire serait de commencer en haut et de regarder tous les titres jusqu'à le trouver. Dans le meilleur des cas c'est le premier roman et on le trouve directement. Dans le pire des cas il se trouve tout en bas et on aura passé beaucoup de temps à chercher dans toute l'étagère. Vous voyez donc que cette recherche, bien que facile à effectuer peut rapidement se retrouver inefficace.

Recherche binaire

Et si au lieu de chercher linéarement dans l'étagère, vous regardez les titres sachant que l'étagère est triée alphabétiquement. Vous n'aurez pas à consulter tous les titres des livres pour trouver votre livre. Vous allez commencer votre recherche à partir d'une lettre sachant que vous avez éliminez beaucoup de romans ce qui vous permettra d' économiser du temps. C'est le concept de la recherche binaire.

Remarque:

La recherche linéaire peut être faite sur des éléments triés et non triés contrairement à la recherche binaire qui exige des éléments triés.

Implementation

On va voir comment ces types de recherche fonctionnent dans le cas d'une liste de nombres.

Recherche linéaire

liste1= [4,3,5,2,5,0,2]

l'algorithme de la recherche du nombre 3:

1. prenez un seul nombre de la liste.
2. comparez le avec 3 et vérifier s'il est 3 ou non:
   1. si oui, retourner True.
   2. si non, retourner False.
3. si vous arrivez à la fin de la liste, retourner False.

def recherchelineaire(liste,val)
    for element in liste:
         if element == val:
              return True
    return False

print(recherchelineaire([4,3,5,2,5,0,2],3)

Recherche binaire

L'idée est de comparer l'élément avec la valeur qui se trouve au milieu. comme ça, avec chaque recherche on va éliminer la moitié de la liste.

L'algorithme:

1. suivez les valeurs indicatrices qui se trouvent au début et à la fin de la liste qui vont être incrémentées où décrémentées pour limiter la partie de la liste ou on devra faire la recherche.
2. trouvez le milieu de la liste: milieu= (la longueur de la liste)/2.
3. comparez la valeur du milieu avec la valeur recherchée.
4. vérifier si la valeur du milieu est inférieur à la valeur recherchée:
   1. si oui, la valeur recherchée doit sûrement être dans la deuxième moitié de la liste.
   2. si non, la valeur recherchée doit sûrement être dans la première moitié de la liste.
5. répéter la même démarche jusqu'à ce qu'on trouve la valeur recherchée ou on arrive à la fin de la liste.

Note:

la liste continue à se diviser en deux et la valeur du milieu est comparée à la valeur recherchée jusqu'à ce qu'on trouve la valeur recherchée ou qu'il n'y ait plus des éléments avec quoi on peut comparer la valeur en question.

Code:

trouvez si la valeur 15 se trouve dans la liste2 = [3, 6,8,9,12,15,18,20].

def recherchebinaire(liste,val):
  debut =  0
  fin = len(liste)-1
  res = False
     
    while debut<=fin and not done:
      milieu = (debut+fin)//2
         if liste[milieu] == val:
             done = True
         else:
            if ls[milieu] > val:
                 fin = fin-1
            else:
                debut = debut+1
    return res
 print(recherchebinaire( [3, 6,8,9,12,15,18,20], 15)

cycle	debut	fin	milieu	liste[milieu]	resultaT
1	0	7	3	9	9<15
2	5	7	6	18	18>15
3	5	6	10	15	15=15

Conclusion

À partir des exemples ci-dessus, vous avez constaté que la recherche binaire est plus rapide que la recherche linéaire. La complexité de la recherche binaire est 0(log(n)), celle de la recherche linéaire est 0(n).

---

Posted on Utopian.io - Rewarding Open Source Contributors

---