Búsqueda en un arreglo ordenado

Una alternativa al método del adversario usado en la búsqueda en un arreglo ordenado es la siguiente. Si un algoritmo toma los objetos de búsqueda como cajas negras y se basa únicamente en comparaciones para tomar sus decisiones, entonces para cada búsqueda de un elemento $A[i]$ distinto deberá obtener una secuencia distinta de resultados a sus comparaciones (las comparaciones que realiza también pueden depender del resultado de comparaciones anteriores). Si existen dos elementos $A[i]$ y $A[j]$ para los cuales el algoritmo obtiene la misma secuencia de resultados, entonces es que realiza las mismas comparaciones y responde lo mismo a ambas búsquedas, lo cual sería incorrecto.

Eso significa que el algoritmo se puede convertir en un codificador para los valores en $[1,n]$. Creo un arreglo ordenado cualquiera $A[1,n]$, y para codificar $i$ pido al algoritmo que busque $A[i]$. Tomo nota de los resultados de las comparaciones que va realizando el algoritmo y los codifico como una secuencia de bits. Para obtener $i$ a partir de ese código (es decir, para "descomprimir" el valor de $i$), simulo el algoritmo, y cuando llega el momento de una comparación, veo qué pasaría si el resultado de la comparación se corresponde con el siguiente bit de la codificación.

Dado que un algoritmo de búsqueda permite codificar cada elemento de $[1,n]$ mediante las comparaciones que realiza, se deduce que en el peor caso debe realizar al menos $\log_2 n$ comparaciones. También esto sugiere que, para llegar a ese peor caso, el algoritmo debe procurar que cada comparación reduzca a la mitad el número de inputs posibles, lo que nuevamente nos lleva a la búsqueda binaria.