[Python-es] Buscar índices de un array (que cumple condición) de forma eficiente

[Daniel Garcia Moreno]

2010/3/4 Pablo Angulo <pablo.angulo en uam.es>:
> Daniel Garcia Moreno escribió:
>>
>> Según mis conocimientos en computación, esta búsqueda es de orden n^2.
>> Si el primer conjunto está ordenado, puede llegar a ser de orden
>> n*log(n) puesto que puedes hacer una búsqueda binaria en lugar de
>> conjunto.index(valor). Y creo que no vas a poder optimizar más por
>> ahí, porque la complejidad del problema es esa.
>>
> Si la lista grande tiene N elementos y la pequeña M, puedes elegir entre
> O(Mlog(N)), usando bisect. o O(N), con la técnica que te decía antes.
>

O puedes combinar las dos, buscar desde el último indice en adelante
pero hacerlo con busqueda binaria.