Il modo più veloce per trovare quali due elementi di un elenco un altro elemento è più vicino a in python

Question

L'input è un elenco ordinato di elementi e un elemento esterno. Per esempio:

list_ = [0, 3.5, 5.8, 6.2, 88] 
item = 4.4 

Qual è il modo più veloce per scoprire quali due elementi in list_item cadute tra? In questo caso, ad esempio, i due numeri sarebbero 3,5 e 5,8. Qualche idea?

Answer 1

Dato che l'input è ordinato, la scelta migliore è quella di utilizzare il modulo bisect, ad es. bisect_left

>>> list_ = [0, 3.5, 5.8, 6.2, 88] 
>>> item = 4.4 
>>> bisect.bisect_left(list_, item) 
2 

Gli elementi che si desidera risiedere indici bisect_left(list_, item) e
bisect_left(list_, item) - 1

Questo dovrebbe dare un risultato in O(logN) ricerche - Non c'è molto di meglio dal punto di vista algoritmo.

Answer 2

È possibile utilizzare bisect module's bisect funzione per ottenere l'indice in cui il item si inserisce in

list_, item = [0, 3.5, 5.8, 6.2, 88], 4.4 
from bisect import bisect 
print bisect(list_, item) 
# 2 

Ricordate vostro list_ deve essere ordinato, per essere in grado di utilizzare le funzioni nel modulo bisect.

Answer 3

userei NumPy:

from numpy import * 
x = array([0, 3.5, 5.8, 6.2, 88]) 
item = 4.4 

i= argmin(abs(x-item)) 
print(i)