Diferencia entre revisiones de «Usuario:Lmorillas/modulo programacion/python/busqueda binaria»
De WikiEducator
(Página creada con '{{MiTitulo|Búsqueda binaria}} Búsqueda optimizada para secuencias ordenadas: <source lang="python"> def busqueda_binaria(v, L): '''Devuelve el índice del la primera ocu…') |
|||
| Línea 15: | Línea 15: | ||
j = m - 1 | j = m - 1 | ||
if 0 <= i < len(L) and L[i] == v: | if 0 <= i < len(L) and L[i] == v: | ||
| + | return i | ||
| + | else: | ||
| + | return -1 | ||
| + | </source> | ||
| + | |||
| + | En Python puedes usar el módulo bisect: http://docs.python.org/library/bisect.html | ||
| + | |||
| + | <source lang="python"> | ||
| + | import bisect | ||
| + | |||
| + | def busqueda binaria(v, L): | ||
| + | 'Devuelve el índice del primer valor v en L. Si no devuelve -1' | ||
| + | i = bisect_left(L, v) | ||
| + | if i != len(L) and L[i] == v: | ||
return i | return i | ||
else: | else: | ||
return -1 | return -1 | ||
</source> | </source> | ||
Última revisión de 23:25 15 feb 2012
Búsqueda optimizada para secuencias ordenadas:
def busqueda_binaria(v, L): '''Devuelve el índice del la primera ocurrencia de v en L o -1 si no está en L''' i = 0 j = len(L) -1 while i != j +1: m = (i+j) / 2 if L[m] < v: i = m + 1 else: j = m - 1 if 0 <= i < len(L) and L[i] == v: return i else: return -1
En Python puedes usar el módulo bisect: http://docs.python.org/library/bisect.html
import bisect def busqueda binaria(v, L): 'Devuelve el índice del primer valor v en L. Si no devuelve -1' i = bisect_left(L, v) if i != len(L) and L[i] == v: return i else: return -1
