Trouver l'indice d'un élément le plus proche de la valeur dans une liste qui n'est pas entièrement triée

Question

A titre d'exemple, ma liste est la suivante :

[25.75443, 26.7803, 25.79099, 24.17642, 24.3526, 22.79056, 20.84866,
 19.49222, 18.38086, 18.0358, 16.57819, 15.71255, 14.79059, 13.64154,
 13.09409, 12.18347, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152,
 6.983734, 6.048035, 5.505096, 4.65799]

et je cherche l'indice de la valeur la plus proche de 11.5 . J'ai essayé d'autres méthodes, telles que la recherche binaire et la recherche d'informations. bisect_left mais ils ne fonctionnent pas.

Je ne peux pas trier ce tableau, car l'index de la valeur sera utilisé sur un tableau similaire pour récupérer la valeur à cet index.

Answer 1

Essayez ce qui suit :

min(range(len(a)), key=lambda i: abs(a[i]-11.5))

Par exemple :

>>> a = [25.75443, 26.7803, 25.79099, 24.17642, 24.3526, 22.79056, 20.84866, 19.49222, 18.38086, 18.0358, 16.57819, 15.71255, 14.79059, 13.64154, 13.09409, 12.18347, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152, 6.983734, 6.048035, 5.505096, 4.65799]
>>> min(range(len(a)), key=lambda i: abs(a[i]-11.5))
16

Ou pour obtenir l'indice et la valeur :

>>> min(enumerate(a), key=lambda x: abs(x[1]-11.5))
(16, 11.33447)

Answer 2

import numpy as np

a = [25.75443, 26.7803, 25.79099, 24.17642, 24.3526, 22.79056, 20.84866, 19.49222, 18.38086, 18.0358, 16.57819, 15.71255, 14.79059, 13.64154, 13.09409, 12.18347, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152, 6.983734, 6.048035, 5.505096, 4.65799]

index = np.argmin(np.abs(np.array(a)-11.5))
a[index] # here is your result

Si a est déjà un tableau, la transformation correspondante peut être omise.

Answer 3

Si vous ne pouvez pas trier le tableau, il n'y a pas de moyen rapide de trouver l'élément le plus proche - vous devez itérer sur toutes les entrées.

Il existe une solution de contournement, mais elle demande beaucoup de travail : Ecrivez un algorithme de tri qui trie le tableau et (en même temps) met à jour un second tableau qui vous indique où se trouvait cette entrée. avant le tableau a été trié.

De cette façon, vous pouvez utiliser la recherche binaire pour rechercher l'index de l'entrée la plus proche et ensuite utiliser cet index pour rechercher l'index original en utilisant le "tableau d'index".

[EDIT] Utilisation de zip() c'est assez simple à réaliser :

 array_to_sort = zip( original_array, range(len(original_array)) )
 array_to_sort.sort( key=i:i[0] )

Vous pouvez maintenant effectuer une recherche binaire de la valeur (en utilisant la fonction item[0] ). item[1] vous donnera l'index original.

Answer 4

Pourquoi ne pas zipper les deux listes, puis trier le résultat ?

Answer 5

Passer en revue tous les éléments n'est que linéaire. Si vous triez le tableau, ce serait pire.

Je ne vois pas de problème à garder une personne supplémentaire deltax (la plus petite différence jusqu'à présent) et idx (l'index de cet élément) et boucle une fois dans la liste.