Dificultad para resolver un código en O (logn)

Escribí una función que obtiene como entrada una lista de entradas únicas en orden (de pequeña a grande). Se supone que debo encontrar en la lista un índice que coincida con el valor en el índice. por ejemplo, si L [2] == 2 la salida es verdadera. así que después de hacer eso en la complejidad O (logn) ahora quiero encontrar cuántos índices se comportan así en la lista dada con la misma complejidad O (logn). Estoy subiendo mi primer código que hace la primera parte y el segundo código con el que necesito ayuda:

def steady_state(L): lower= 0 upper= len(L) -1 while lowermiddle_i: upper= middle_i-1 else: lower= middle_i +1 return None def cnt_steady_states(L): lower= 0 upper= len(L) -1 a=b=steady_state(L) if steady_state(L)== None: return 0 else: cnt=1 while True: if L[upper] == upper and a=lower: cnt+= b- lower lower = b 

No es posible con las restricciones que has dado todavía. La mejor complejidad que puede lograr teóricamente es O ( n ).

O () asume el peor de los casos (solo una definición, puede dejar esa parte). Y en el peor de los casos, siempre tendrá que mirar cada elemento para verificar que sea igual a su índice.

El caso cambia si tiene más restricciones (por ejemplo, los números son todos ints y ninguno puede aparecer más de una vez, es decir, no hay dos números consecutivos iguales). Tal vez este es el caso?

EDITAR:

Después de escuchar que, de hecho, se aplican mis restricciones asumidas (es decir, solo instrucciones que aparecen una vez). Ahora propongo este enfoque: Puede asumir con seguridad que solo puede tener un rango continuo en el que se encuentran todas las entradas coincidentes. I. e. solo necesitas encontrar un límite inferior y un límite superior. El resultado deseado será el tamaño de ese rango.

Cada límite se puede encontrar de forma segura mediante una búsqueda binaria, de las cuales cada una tiene O (log n ).

 def binsearch(field, lower=True, a=0, b=None): if b is None: b = len(field) while a + 1 < b: c = (a + b) / 2 if lower: if field[c] < c: a = c else: b = c else: # search for upper bound if field[c] > c: b = c else: a = c return b if lower else a def indexMatchCount(field): upper = binsearch(field, lower=False) lower = binsearch(field, b=upper+1) return upper - lower + 1 

Esto utilicé para la prueba:

 field = list({ random.randint(-10, 30) for i in range(30) }) field.sort() upper = binsearch(field, lower=False) lower = binsearch(field, b=upper+1) for i, f in enumerate(field): print lower <= i <= upper, i == f, i, f 

Suponiendo que los enteros negativos están bien:

Creo que la clave es que si obtiene un valor menor que su índice, sabe que todos los índices a la izquierda tampoco coinciden con su valor (ya que los enteros están aumentando estrictamente). Además, una vez que obtiene un índice cuyo valor es mayor que el índice, todo a la derecha es incorrecto (el mismo motivo). Luego puede hacer un algoritmo de dividir y conquistar como lo hizo en el primer caso. Algo a lo largo de las líneas de:

 check middle index: if equal: count = count + 1 check both halves, minus this index elif value > index: check left side (lower to index) elif index > value: check right side (index to upper) 

En el peor de los casos (cada índice coincide con el valor), todavía tenemos que verificar cada índice.

Si los enteros no son negativos, entonces usted sabe aún más. Ahora también sabe que si un índice coincide con el valor, todos los índices a la izquierda también deben coincidir con el valor (¿por qué?). Por lo tanto, se obtiene:

 check middle index: if equal: count = count + indices to the left (index-lower) check the right side (index to upper) elif value > index: check left side (lower to index) elif index > value: ##Can't happen in this case 

Ahora nuestro peor caso ha mejorado significativamente. En lugar de encontrar un índice que coincida y no obtener ninguna información nueva de él, obtenemos una tonelada de información cuando encontramos uno que coincida, y ahora sabemos que la mitad de los índices coinciden.

Si “todos los números son ints y aparecen solo una vez”, entonces simplemente puede hacer una búsqueda binaria para el primer par de números donde L[i]==i && L[i+1]!=i+1 .

Para permitir entradas negativas, verifique si L[0]<0 , y si es así, busque entre 1..N para:
i>0 && L[i]==i && L[i-1]!=i-1 . A continuación, realice la búsqueda anterior entre i y N.