Bonjour,
Je recherche une approche efficace pour résoudre le problème suivant:
Sur l'ensemble d'entiers [[0, X]], je dispose d'un ensemble d'intervalles en cardinal limité (disons < 10).
Je cherche une approche me permettant de tester rapidement si une valeur est incluse dans au moins un des intervalles de l'ensemble.
Exemple: Soit les intervalles entiers [[0, 4]], [[6, 12]], [[100, 110]].
Je désire soumettre une valeur à une fonction de telle sorte que celle-ci me renvoie si un intervalle de l'ensemble d'intervalles contienne cette valeur.
Ma première implémentation consiste à maintenant une liste d'intervalle et à parcourir linérairement cette liste, en arretant la recherche dès qu'à été trouvé un intervalle contenant la valeur a été trouvé (renvoie alors vrai) ou si la fin de la liste est atteinte (renvoie faux).
Cependant, la complexité est en O(n), n étant la taille de la liste.
Une autre solution que j'ai envisagé est de trier la liste d'intervalle par bornes inférieures croissantes. Alors, par tri dichotomique, on trouve l'intervalle dont la borne inférieure est juste avant la valeur à tester en o(ln(n)).
Une autre solution que j'ai envisagée consiste à exprimer l'ensemble d'intervalles par un tableau de booléens. La taille de ce tableau serait de X+1 (pour chaque valeur de 0 à X) et chaque case de ce tableau d'indice i spécifie si la valeur entière i est dans un intervalle. La complexité est alors en o(1) mais l'occupation mémoire inacceptable.
N'ayant pas trouver de littérature concernant ce problème, avez-vous d'autres approches à me suggérer?
Vous remerciant par avance,
Cordialement,
Benoît.
Partager