Búsqueda en un arreglo

Como un caso muy simple, que ni siquiera requiere de un modelo, consideremos el problema de encontrar dónde está un determinado elemento en un arreglo desordenado (supongamos que sabemos que está, pero no dónde). Para resolver este problema, cualquier algoritmo debe examinar las $n$ celdas del arreglo, pues si un algoritmo dejara alguna celda sin leer, el adversario colocaría allí al elemento buscado. Es decir, el adversario responde con elementos distintos al buscado cada vez que el algoritmo accede a una celda del arreglo, a menos que sea la última celda restante. Esto es una abstracción del hecho de que, sea cual sea la estrategia del algoritmo para examinar las celdas, hay un input en el cual el elemento estará en una de las celdas no examinadas, por lo cual en el peor caso es necesario examinarlas todas.

Arreglo ordenado

Si el arreglo está ordenado, el adversario ya no puede obligar al algoritmo a examinar todas las celdas, pues debe ser consistente: si entrega un determinado elemento $A[i]=x$, entonces debe entregar elementos $\le x$ en celdas $< i$, y elementos $\ge x$ en celdas $> i$. Por ello, no tenemos una cota inferior de $n$ comparaciones en este caso.

Para encontrar una cota en el caso ordenado, usaremos el siguiente modelo. Todo algoritmo realiza una serie de accesos a $A$ hasta responder, y contaremos sólo la cantidad de esos accesos como su costo. El modelo es que el algoritmo sabe que el elemento buscado tiene que estar en un rango $A[i,j]$ del arreglo original $A[1,n]$. Mediante acceder a un elemento $A[k]$, puede ser que: (1) $k \not\in [i,j]$, en cuyo caso el algoritmo no aprende nada; (2) $A[k]$ es el elemento buscado, en cuyo caso el algoritmo ahora sabe que el elemento está en el rango $A[k,k]$; (3) $A[k]$ sea mayor que el elemento buscado, en cuyo caso el algoritmo ahora sabe que el elemento está en el rango $A[i,k-1]$; y (4) $A[k]$ sea menor que el elemento buscado, en cuyo caso el algoritmo ahora sabe que el elemento buscado está en el rango $A[k+1,j]$.

El estado inicial es $A[1,n]$ y los estados finales son todos los rangos $A[k,k]$, $1 \le k \le n$. Podemos ver por inducción que el algoritmo nunca ha mirado un elemento dentro del rango actual $A[i,j]$, por lo cual el adversario es libre de decidir entre las alternativas (2), (3) y (4) (el algoritmo elige el $k$, por lo cual nunca cometerá la tontería de elegir (1)). El adversario intentará que el rango se mantenga lo mayor posible, pues al llegar a tamaño 1 el algoritmo llega a un estado final. Por ello, nunca elegirá (2). Elegirá (3) si $k-i \ge j-k$ y (4) si no. Esto garantiza que el intervalo se reduce a lo sumo a la mitad en cada iteración (cuando tiene largo par), por lo cual cualquier algoritmo requiere en el peor caso $\lfloor \log_2 n\rfloor$ comparaciones (requiere una más si no se sabe si el elemento está en $A$).

Cotas superiores

En ambos casos, arreglo desordenado y ordenado, sabemos que las cotas inferiores son ajustadas porque conocemos la búsqueda secuencial y binaria, que dan cotas superiores iguales a las inferiores. Pero en general este método no tiene por qué dar cotas inferiores ajustadas. Por ejemplo, puede que hayamos elegido un modelo que no representa todo lo que el algoritmo debe aprender sobre el input para contestar correctamente, por lo que le permite llegar del estado inicial a uno final a un costo inferior al del algoritmo óptimo. También puede que el adversario no sea lo suficientemente inteligente y no fabrique el peor input posible para el algoritmo.

En el caso del arreglo ordenado se nota otro aspecto importante de esta técnica: suele sugerir lo que debería hacer un algoritmo óptimo. En este caso, nos queda claro que lo mejor es consultar a la mitad del intervalo, pues de otro modo el adversario hará que nuestro intervalo se reduzca más lentamente. Es decir, nos sugiere el algoritmo de búsqueda binaria.