Diviser pour régner

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 Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :