Revisión de código

Revisa este código de un agente

Un agente propone buscar en una lista enlazada ordenada con búsqueda binaria, «para que sea O(log n)»:

Texto

función buscar(lista, x):    bajo ← 0; alto ← longitud(lista)    mientras bajo < alto:        medio ← bajo + (alto − bajo) / 2        si leer(lista, medio) < x: bajo ← medio + 1        si no: alto ← medio    devolver bajo

Un agente propone buscar en una lista enlazada ordenada con búsqueda binaria, usando leer(lista, medio), «para que sea O(log n)». ¿Cuánto cuesta de verdad?Más que la lineal: hasta O(n log n) saltos, porque cada leer(lista, medio) recorre desde la cabezaO(n), igual que la lineal, porque en el peor caso las dos terminan recorriendo la lista una vezO(log n), porque la lista ordenada permite saltar al nodo del medio con su enlaceO(log n), porque la búsqueda binaria descarta la mitad en cada paso, sea cual sea la estructura