python - and - searching algorithms

¿Buscando una lista ordenada?

Question

¿Qué es una forma pitónica de buscar o manipular sequence ordenadas?

Answer 1

Pitón:

def find_elem_in_sorted_list(elem, sorted_list):
# https://docs.python.org/3/library/bisect.html
''Locate the leftmost value exactly equal to x''
i = bisect_left(sorted_list, elem)
if i != len(sorted_list) and sorted_list[i] == elem:
return i
return -1

Answer 2

Vale la pena señalar que hay un par de bibliotecas de Python de alta calidad para mantener una lista ordenada que también implementa búsqueda rápida: sortedcontainers y blist . El uso de estos depende, por supuesto, de la frecuencia con la que esté insertando / eliminando elementos de la lista y necesitando buscar. Cada uno de esos módulos proporciona una clase SortedList que mantiene eficientemente los elementos en orden de clasificación.

De la documentación de SortedList:

L.bisect_left(value)
Similar to the bisect module in the standard library, this returns
an appropriate index to insert value in L. If value is already present
in L, the insertion point will be before (to the left of) any existing
entries.
L.bisect(value)
Same as bisect_left.
L.bisect_right(value)
Same as bisect_left, but if value is already present in L, the
insertion point will be after (to the right of) any existing entries.

Ambas implementaciones utilizan la búsqueda binaria para encontrar el índice correcto del valor dado. Hay una página de comparación de rendimiento para elegir entre los dos módulos.

Descargo de responsabilidad : Soy el autor del módulo de contenedores ordenados.

Answer 3

bisect es parte de la biblioteca estándar, ¿es ese el tipo de cosa que estás buscando?