Buscar el próximo artículo más bajo en una lista ordenada

Question

digamos que tengo una lista ordenada de flotadores. Ahora me gustaría obtener el índice del próximo artículo más bajo de un valor dado. La habitual aproximación for-loop tiene una complejidad de O (n). Como la lista está ordenada, debe haber una manera de obtener el índice con O (log n).

Mi O (n) Enfoque:

index=0 
for i,value in enumerate(mylist): 
    if value>compareValue: 
     index=i-1 

¿Existe un tipo de datos para la solución de ese problema en O (log n)?

mejores deseos Sebastian

Answer 1

Usted puede hacer una búsqueda binaria en un array/list para obtener el índice del objeto que está buscando y obtener el índice por debajo de él para conseguir la entrada inferior (dado que no existe en realidad es una entrada más baja!).

Ver: Binary search (bisection) in Python

Tenga cuidado al comparing floating point numbers por la igualdad!

Answer 2

Para responder parte de la pregunta acerca de los tipos de datos: En un sentido general, el tipo de datos más apropiado para encontrar cosas en O (log n) el tiempo es el árbol binario (manteniendo al mismo tiempo O (1) el rendimiento de las inserciones y eliminaciones!) . Puedes encontrar cosas en él haciendo una serie de decisiones de izquierda a derecha, que es muy similar a la forma en que realizas una búsqueda binaria en una lista lineal, pero es (IMO) un poco más intuitiva desde el punto de vista conceptual.

Dicho esto, por lo poco que sé de Python, los árboles binarios no parecen estar en la biblioteca estándar del lenguaje. Para su aplicación, probablemente no sería beneficioso incluir una implementación solo para este propósito.

Finalmente, los árboles binarios y la búsqueda binaria en una lista ordenada le permitirán acortar la búsqueda en un paso: no es necesario buscar el elemento clave y luego volver a su predecesor. En cambio, en cada paso de comparación, si encuentra el valor clave, actúe como si fuera demasiado grande. Esto hará que su búsqueda termine en el siguiente valor más pequeño. Hecho con cuidado, esto también puede ayudar con el problema de "casi el valor del punto flotante" mencionado por bart.

Answer 3

¿Qué tal bisect?

>>> import bisect 
>>> float_list = [1.0, 1.3, 2.3, 4.5] 
>>> i = bisect.bisect_left(float_list, 2.5) 
>>> index = i - 1 
>>> index 
2 

Puede que tenga que manejar el caso de un valor de búsqueda inferior o igual al valor más bajo/más a la izquierda en la lista por separado (index == -1 en este caso).

Según el índice que desee tener en caso de igualdad, puede que tenga que usar bisect_right en su lugar.

Answer 4

Utilice el módulo bisect. La función

bisect.bisect_left(mylist, compareValue) 

devuelve el punto de inserción adecuado para el elemento en la lista para mantener el orden ordenado.

Answer 5

import bisect 

def next_lower_value(values_list, input_value): 
    index= bisect.bisect_left(values_list, input_value) 
    if index == 0: # there's not a "next lower value" 
     raise NotImplementedError # you must decide what to do here 
    else: 
     return values_list[index - 1] 

>>> l= [11, 15, 23, 28, 45, 63, 94] 
>>> next_lower_value(l, 64) 
63 
>>> next_lower_value(l, 63) 
45 
>>> next_lower_value(l, 1000) 
94 
>>> next_lower_value(l, 1) 
Traceback (most recent call last): 
    File "<pyshell#29>", line 1, in <module> 
    next_lower_value(l, 1) 
    File "<pyshell#26>", line 4, in next_lower_value 
    raise NotImplementedError # you must decide what to do here 
NotImplementedError 

Dado que usted solicita el índice y no el siguiente valor más bajo, cambiar la función next_lower_value para volver index - 1 en lugar de values_list[index - 1].

Answer 6

Si leo esto a la derecha, el siguiente artículo más bajo es el primer elemento de la lista que es menor o igual a x. El bisect documentation for searching sorted lists da esta función:

def find_le(a, x): 
    'Find rightmost value less than or equal to x' 
    i = bisect_right(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError