Najszybszy sposób na znalezienie dwóch elementów listy, które znajdują się najbliżej w pythonie

Question

Dane wejściowe są posortowaną listą elementów i elementem zewnętrznym. Na przykład:

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

Jaki jest najszybszy sposób na znalezienie się czego dwa elementy list_item przypada między? W tym przypadku na przykład dwie liczby to 3,5 i 5,8. Jakieś pomysły?

Answer 1

Ponieważ dane wejściowe są posortowane, najlepiej jest algorytmicznie zastosować moduł bisect - np. bisect_left

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

elementy, które mają znajdować się w indeksach bisect_left(list_, item) i
bisect_left(list_, item) - 1

To powinno dać rezultat w O(logN) wyszukiwań - Nie ma się o wiele lepiej niż z punktu widzenia algorytmu.

Answer 2

Można użyć bisect module's bisect funkcję, aby uzyskać indeks, w którym item pasuje w

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

Pamiętaj Twój list_ musi być sortowane, aby móc korzystać z funkcji w module bisect.

Answer 3

użyłbym numpy:

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

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