Algorithmique Dichotomie Fermé

Question

Bonjour, 
j'ai un exercice qui est :
Ecrire une fonction qui indique si un entier Val est présent dans une tableau T d'entiers à une dimension de taille N.Utiliser une recherche par dichotomie.(le tableau est bien entendu trié par ordre croissant)

J'ai fait cette Fonction : (je suis quasiment certain qu'elle est bonne, mais je suis sure qu'elle peut être amélioré)

Fonction Rechercher (T, N, Val) : booléen
Paramètres par valeur : T : Tableau [1..N] d'entiers
----------------------------Val, N : Entiers
Variables : Deb, Fin : Entiers
-------------Flag : booléen
Début
-----------Deb <== 1
-----------Fin  <== N
-----------Flag <== Faux
---Répéter 
---------------N <== (Deb + Fin) div 2
---------------Si T[N] = Val Alors
---------------------Flag <== vrai
---------------Sinon
---------------------Si Val < T[N] Alors
--------------------------Fin <== N
---------------------Sinon
--------------------------Deb <== N
---------------------Finsi
---------------Finsi
---jusqu'à [Deb = (Fin-1)] ou Flag = vrai
---Si Flag = vrai Alors
-------Retourner Flag
---Sinon
-------Si T[Deb] = Val ou T[Deb + 1] = Val Alors
------------Flag <== vrai
-------Finsi
---Finsi
---Retourner Flag
Fin 

Pouvez vous me conseiller ?
Merci !

Configuration: Windows 7 / Chrome 23.0.1271.64

KX · Answer

Je n'ai pas regardé en détail vu que tu es sûr que ta fonction est bonne, mais une amélioration est de penser récursif, ça simplifie le code (et l'esprit) :

C'est à dire appeler la fonction dans elle même :

Fonction Rechercher(T, N, Val) : Booléen
    Retourner Rechercher_Recursif(T,Val,1,N)
Fin

Fonction Rechercher_Recursif(T,Val,Deb,Fin) : Booléen
    Si (Deb >= Fin)
        Alors Retourner (Val = T[Start])
    Sinon
        Milieu <== (Deb+Fin)/2
        Si (Val = T[Milieu])
            Alors Retourner Vrai
        Sinon Si (Val < T[Milieu])
            Alors Retourner Rechercher_Recursif(T,Val,Deb,Milieu-1)
        Sinon
            Retouner Rechercher_Recursif(T,Val,Milieu+1,Fin)
        FinSi
    FinSi
FinLa confiance n'exclut pas le contrôle

Dredge3 · Answer

Bah justement j'aimerais éviter la récursivité (vu que je sais comment faire). 
Tu peux regarder vite fait l'algorithme si tu as le temps ?
(Car je ne suis même pas sure qu'il soit correct)

Algorithmique Dichotomie

2 réponses

Discussions similaires