índice hallazgo de un elemento más cercano al valor en una lista que no está del todo ordenadas

Question

Como ejemplo mi lista es:

[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] 

y estoy buscando el índice del valor más cercano a 11.5. He intentado con otros métodos, como la búsqueda binaria y bisect_left, pero no funcionan.

No puedo ordenar esta matriz, porque el índice del valor se usará en una matriz similar para obtener el valor en ese índice.

Answer 1

intente lo siguiente:

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

Por ejemplo:

>>> 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 

O para obtener el índice y el valor:

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

Answer 2

¿Qué le parece: usted comprime las dos listas, luego ordena el resultado?

Answer 3

Si no puede ordenar la matriz, entonces no hay una forma rápida de encontrar el elemento más cercano: debe iterar sobre todas las entradas.

Hay una solución, pero es un poco de trabajo: Escribir un algoritmo de ordenamiento que ordena la matriz y (al mismo tiempo) actualiza una segunda matriz que le dice donde se antes se solucionó la matriz esta entrada.

De esta manera, puede usar la búsqueda binaria para buscar el índice de la entrada más cercana y luego usar este índice para buscar el índice original usando la "matriz de índice".

[EDIT] Usando zip(), esto es bastante fácil de lograr:

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

Ahora se puede búsqueda binaria para el valor (utilizando item[0]). item[1] le dará el índice original.

Answer 4

Yendo a través de todos los artículos es solo lineal. Si clasificaras la matriz, sería peor.

No veo un problema en mantener un deltax adicional (la diferencia mínima hasta ahora) y idx (el índice de ese elemento) y solo un ciclo una vez a través de la lista.

Answer 5

Tenga en cuenta que si el espacio no es importante, puede ordenar cualquier lista sin mover los contenidos creando una lista secundaria de los índices ordenados.

También tenga en cuenta que si hace esto solo una vez, tendrá que atravesar cada elemento de la lista O (n). (Si varias veces entonces es probable que se desee ordenar para aumentar la eficiencia más adelante)

Answer 6

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 

En caso de que una es ya una matriz, la transformación correspondiente puede omitirse.