buscar valores antes y después en una larga lista ordenada

Question

¿Cuál sería la forma más rápida de buscar un número (por ejemplo, 12.31) en una lista ordenada larga y obtener los valores uno antes y después de mi valor de "búsqueda" cuando el exacto no se encuentra el valor (por ejemplo, 11.12 y 12.03 en la lista a continuación)?
Muchas gracias de antemano.

long_list = [10.11, 11.12, 13.03, 14.2 .. 12345.67] 

Answer 1

El más rápido es probable que utilice el soporte incorporado en Python. Aquí estoy pensando en el módulo bisect. A continuación estoy usando un diccionario para registrar rápidamente O (1) si hay un valor en la lista; si no, bisect se usa para encontrar valores más pequeños que y mayores que el valor buscado.

#!/usr/bin/env python 

import bisect 

def find_lt(a, x): 
    'Find rightmost value less than x' 
    i = bisect.bisect_left(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError 

def find_gt(a, x): 
    'Find leftmost value greater than x' 
    i = bisect.bisect_right(a, x) 
    if i != len(a): 
     return a[i] 
    raise ValueError 

# First create a test-list (49996 items) 
i=1.0 
R=[1.0] 
D={} 
while i < 10000: 
    i+=0.2 
    i=round(i,2) 
    D[i]=True 
    R.append(i) 

# Locate a value, in this case 100.3 which is not in the list 
x=100.3 
if D.has_key(x): 
    print "found", x 
else: 
    print find_lt(R, x) 
    print find_gt(R, x) 

salida para x=100.3:

100.2 
100.4 

Answer 2

Si su lista está ordenada como en su ejemplo, supongo que una búsqueda binaria sería la más rápida.

Answer 3

La búsqueda exponencial (AKA búsqueda al galope) funcionaría mejor que la búsqueda binaria simple si la lista es muy larga. La idea es escanear hacia adelante desde la posición 0 al aumentar los pasos hasta que se pase la respuesta, en este punto se puede realizar una búsqueda binaria hasta el rango formado por los dos últimos pasos. Si no se encuentra el elemento, el último intento apuntará a los elementos más cercanos.

Eche un vistazo a Basic Techniques for information retrieval. Se proporciona el algoritmo de pseudocódigo y analizan su complejidad frente a la búsqueda binaria.

Answer 4

li = [10.11, 11.12, 13.03, 14.2, 15.6, 15.8, 17.9, 12345.67] 

def searsh(x,li): 
    itli = iter(li) 
    a = itli.next() 
    if a==x: 
     return a 
    else: 
     while True: 
      b = itli.next() 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      a = itli.next() 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a) 


print searsh(13.5,li) 
print searsh(10.11,li) 
print searsh(50.3,li) 
print searsh(12345.67,li) 

resultado

(13.03, 14.2) 
10.11 
(17.9, 12345.67) 
12345.67 

también:

def searsh(x,li): 
    a = li[0] 
    if a==x: 
     return a 
    else: 
     j = 0 
     while True: 
      j += 1 
      b = li[j] 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      j += 1 
      a = li[j] 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a)