Algorithme simple de recherche de valeur ou juste avant dans tableau trié

Bonjour,

J'ai tenté d'écrire une fonction qui permet, pour un tableau déjà trié - et dont la première valeur est toujours zéro, de trouver la position de la valeur juste inférieure ou égale à la valeur recherchée.

C'est à dire, pour un tableau contenant [0,10,20,30] :
Si recherche 10, me retourne la position 1
Si recherche 11, me retourne la position 1
Si recherche 20, me retourne la position 2
Si recherche 29, me retourne la position 2
Si recherche 39, me retourne la position 3

J'ai fait ceci en C# :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public static int QuickFindAfter_1( List<int> sorted_array, int to_find ) { int deb = 0; int fin = sorted_array.Count ; int milieu = fin / 2 ; int prev = milieu;   while ( deb < fin ) { var current_val = sorted_array[milieu];   if ( to_find >= current_val ) { deb = milieu + 1; } else { fin = milieu - 1; }   prev = milieu; milieu = (fin+deb) / 2; // ATTENTION: Division arrondi au chiffre inférieur }   return Math.Max( prev , milieu ) - 1; }

---

Ca a l'air de pas trop mal marché...mais est-ce que vous voyez mieux ?
Il y a par exemple l'utilisation du Max qui n'est pas terrible...

VOus remerciant par avance.
++
TSalm

Quelque chose comme ça ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public static int QuickFindAfter_1( List<int> sorted_array, int to_find ) { int i;   int fin = sorted_array.Count ;   for( i = 1 ; i < fin ; i++ ) { var current_val = sorted_array[i];   if ( to_find > current_val ) { return i -1; } }   return fin - 1; }

---

A noter que ce n'est pas hyper rapide car ça doit comparer toutes les premières valeurs jusqu'à ce qu'il en trouve une qui soit supérieure à celle recherchée donc assez sûrement bien moins rapide que la méthode de dichotomie que tu semble utiliser
(mais ça devrait pouvoir être modifier pour gérer ça via dichotomie plutôt de tester les valeurs du tableau une par une jusqu'à en trouver une supérieure [ou donner l'index de la dernière valeur si aucun n'est trouvé])

Ca fonctionne mais ... c'est effectivement plutôt lent.
Ma question portait surtout sur un algo optimisé en terme de vitesse.

Mais merci pour la réponse.

Non, mon code ne fonctionne pas.
Après prospection, c'est ce code qui fonctionne et qui est plutôt optimisé:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public static int QuickFindAfter_3( List<int> sorted_array, int to_find ) { int deb = 0; int fin = sorted_array.Count ; int milieu = fin >> 1 ; // Division par 2   while ( deb < fin ) {   if ( to_find >= sorted_array[milieu] ) { deb = milieu + 1; } else { fin = milieu - 1; }   milieu = (fin+deb) >> 1; // Division par 2 }   // Plusieurs cas : // - On était supérieur et on a testé la valeur inférieure => retourné la dernière // - On est juste sur la valeur => retourné la dernière // - On était inférieure et on a testé une valeur supérieure => retourné la dernière - 1 // - Plus cas exceptionnel de la valeur qui est supérieure à la dernière occurence if ( milieu == sorted_array.Count ) return milieu - 1; else if ( sorted_array[milieu] <= to_find ) return milieu; else return milieu - 1; }

---

Dans la logique: je garde le fonctionne de la recherche dichotomique. Je sais que le dernier peut être sur la valeur, ou juste avant, ou juste après. Je rajoute donc ces tests à la fin. C'est plus rapide que de maintenir une variable temporaire de dernière valeur.
Optimisation de la division par 2 (remplacé par un décalage binaire)

Mais si quelqu'un trouve mieux ;-)

Tu pourrais par exemple commencer par vérifier les cas limites dès le début :

si la première valeur du tableau est >= to_find alors retourner 0

si la dernière valeur du tableau est < to_find alors retourner sorted_array.Count -1

Et ne faire qu'ensuite ta recherche en dichotomique

Dans pas mal de cas, l'algo se terminera très rapidement (cas des limites)

Dans les autres ca, ça pourrait peut-être éviter de devoir faire les if else if else imbriqués de la fin
(au pire supprimer les 2 else de la fin, car si on arrive à un else c'est que l'on n'a pas rencontré l'autre cas qui fait le return juste avant ...)

Ca devrait donner qqchose du style :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public static int QuickFindAfter_3( List<int> sorted_array, int to_find ) { int deb = 0; int fin = sorted_array.Count ; int milieu = fin >> 1 ; // Division par 2   // cas limites if ( sorted_array[0] >= to_find) return 0; if ( sorted_array[fin-1] < to_find ) return fin -1;   // la méthode dichotomique while ( deb < fin ) {   if ( to_find >= sorted_array[milieu] ) { deb = milieu + 1; } else { fin = milieu - 1; }   milieu = (fin+deb) >> 1; // Division par 2 }   // gestion du "bon milieu" if ( milieu == sorted_array.Count ) return milieu - 1; if ( sorted_array[milieu] <= to_find ) return milieu; return milieu - 1; }

---

(je n'ai pas du tout testé ce code => ça ne marche peut-être donc pas)

Cette idée de cas limites n'est pas bêtes si on a de grandes probabilités de présentation de ces cas limites.

Par contre, je ne crois pas qu'il y a une différence de vitesse d'exécution entre

Code:

---

1 2 3 4 5 6

if pred1 return x1; if pred2 return x2; return x3;

---

Et

Code:

---

1 2 3 4 5 6 7

if pred1 return x1; else if pred2 return x2; else return x3;

---

Je trouve juste que la 2ème syntaxe représente mieux la logique.

Merci en tout cas.
Je vais passer la question en résolu, m^me si je suis convaincu qu'on peut faire mieux (sans passer par du multithreading ;-) )

Bonjour,

regarder les cas limites semble important en effet.

Sinon, il pourrait s'avérer payant, d'essayer d'adapter l'algorithme de la sécante. A la place de prendre les milieux des intervalles lors des itérations, l'algo prend la sécante à val_du_vecteur[] et valeur_a chercher.

Son efficacité dépend de la distribution des valeurs (pour les fonctions fortement concaves ou fortement convexes, c'est pas top), mais dans beaucoup de cas, ce sera plus performant que la dichotomie.
Aussi, mieux vaut ne pas avoir deux fois les même valeurs au sein de ton tableau.

Comparé à la dichotomie, il suffirait de changer le calcul de milieu pour arriver à qque chose du genre:

Code:

---

milieu = deb - sorted_array[deb] * ( fin - deb) / (sorted_array[fin]-sorted_array[deb])

---

Modulo que tu bosses avec des entiers (donc penser à multiplier d'abord et éventuellement passer le numérateur en float), bref, adapte le à ton cas, mais ça peut valoir le coup d'essayer.