Búsqueda binaria

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