Diviser pour régner

Appelez-nous au numéro (+212) 616 374 790 ou écrivez-nous à essaddouki@gmail.com

Demander le soutien en ligne de l'un de nos professeurs, à toute heure et où vous voulez, de 8h à minuit (GMT) Détails

la recherche dichotomique

Problème ! Etant donné un tableau trié tab[] de n éléments, écrivez une fonction pour rechercher un élément donné x dans tab[].

Une approche simple consiste à effectuer une recherche linéaire. La complexité temporelle de l'algorithme ci-dessus est O (n). Une autre approche pour effectuer la même tâche consiste à utiliser la recherche binaire.
La recherche dichotomique consiste à rechercher dans un tableau trié en divisant de manière récursive l'intervalle de recherche en deux.
Commencez par un intervalle couvrant tout le tableau. Si la valeur de la clé de recherche est inférieure à l'élément situé au milieu de l'intervalle, limitez l'intervalle à la moitié inférieure. Sinon, le réduire à la moitié supérieure. Vérifiez à plusieurs reprises jusqu'à ce que la valeur soit trouvée ou que l'intervalle soit vide.

L’idée de la recherche dichotomique est de profiter du tableau trié et de réduire la complexité à O(Log n).

Implémentation récursive de la recherche dichotomique

Nous ignorons initialement la moitié des éléments juste après une seule comparaison.
  1. Comparez x avec l'élément du milieu.
  2. Si x correspond à l'élément du milieu, nous retournons l'indice du milieu.
  3. sinon Si x est supérieur à l'élément milieu, alors x ne peut se situer que dans la moitié droite du sous-tableau après l'élément milieu.
  4. Sinon recherchez dans la moitié gauche.
                def RechercheDicho(tab, debut, fin, x):

                    if fin >= debut:
                        milieu = (debut + fin)//2
                
                        if tab[milieu] == x:
                            return milieu
                
                        elif tab[milieu] > x:
                            return RechercheDicho(tab, debut, milieu-1, x)
                        else:
                            return RechercheDicho(tab, milieu + 1, fin, x)
                    else:
                        return -1
                
                # tester la fonction
                tab = [2, 7, 8, 20, 25, 30, 33, 39, 45, 50]
                x = 8
                
                resultat = RechercheDicho(tab, 0, len(tab)-1, x)
                
                if resultat != -1:
                    print("L'élément est présent à l'indice % d" % result)
                else:
                    print("L'élément n'est pas présent dans le tableau")
                
            
        L'élément est présent à l'indice  2
      

Implémentation itérative de la recherche dichotomique

    def RechercheBinaire2(tab, x):
        debut, fin = 0, len(tab)
        while debut <= fin:
    
            milieu = (debut + fin)//2
            if tab[milieu] == x:
                return milieu
    
            elif tab[milieu] < x:
                debut = milieu + 1
    
            else:
                fin = milieu - 1
    
        # l'element n'existe pas
        return -1
    
    
    tab = [2, 7, 8, 20, 25, 30, 33, 39, 45, 50]
    x = 8
    
    result = RechercheBinaire2(tab, x)
    
    if result != -1:
        print("L'élément est présent à l'indice % d" % result)
    else:
        print("L'élément n'est pas présent dans le tableau")
L'élément est présent à l'indice  2

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :