recherche ternary TERNAIRE :
C'est similaire à la recherche binaire où nous divisons le tableau en deux parties mais dans cet algorithme. En cela, nous divisons le tableau donné en trois parties et déterminons lequel a la clé (élément recherché). Nous pouvons diviser le tableau en trois parties en prenant mid1 et mid2 qui peuvent être calculés comme indiqué ci-dessous. Initialement, l et r seront respectivement égaux à 0 et n-1, où n est la longueur du tableau.
Divisons le tableau en trois parties utilisant mid1 et mid2 :
- mid1 = l + (r-l) / 3
- mid2 = r - (r-l) / 3
- Tout d'abord, nous comparons la clé avec l'élément à mid1 et mid2. S'il est égal, nous retournons mid1 ou mid2.
- Sinon, nous vérifions si la clé est inférieure à l'élément à mid1. Si oui, revenez à la première partie.
- Sinon, nous vérifions si la clé est supérieure à l'élément à mid2. Si oui, revenez à la troisième partie.
- Sinon, nous revenons à la deuxième partie (au milieu).
Function iterative
Function ternary(L:entire, r:entire, key:entire, arr[]:entire) :entire
Var mid1, mid2: entire;
Debut
Tant que (r>=L)
Mid1ß L+(r-L)/3;
Mid2ßr-(r-L)/3;
Si (arr[mid1]= key) alors retourner mid1 ; finsi
Si arr[mid2]=key alors retourner mid2 ; finsi
Si key < arr[mid1] alors rßmid1-1;
Sinon si key >arr[mid2] alors L=mid2+1;
Sinon
Lßmid1+1;
Rßmid2-1;
Retourner -1;
Fonction ternary(L :entier, r :entier, key :entier, arr[] :entier) : entier
Var mid1, mid2 :entier
Debut
Si (r>=L) alors mid1ß L+(r-L)/3 ;
Mid2ß r-(r-L)/3 ;
Si (arr[mid1]= key) alors retourner mid1 ; finsi
Si arr[mid2]=key alors retourner mid2 ; finsi
Si (key<arr[mid]) alors retourner ternary(L, mid1-1, key, arr[]); finsi
Sinon si (key>arr[mid2]) alors retourner ternary (mid2+1, r,key,ar[])
Sinon retourner ternary(mid1+1, mid2-1, key, arr[])
Finsi
// -1 element non trouvé
Retourner -1;
Complexité : Log3n