Algoritmo de búsqueda

Un algoritmo de búsqueda es un conjunto de instrucciones que están diseñadas para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

consiste en buscar un estado concreto entre un conjunto determinado, al que se le llama espacio de estados. Imaginemos, por ejemplo, una habitación con baldosines en la que hay un libro. Un robot se desea desplazar por la habitación con el fin de llegar a dicho libro. ¿De qué manera lo hará? En este punto es donde entran en juego las estrategias y los algoritmos de búsqueda.

Cuando el sistema agente (en este caso, el robot) posee algún tipo de información del medio, se utilizan técnicas de búsquedas informadas; sin embargo, si carece de conocimiento alguno, se deberán emplear algoritmos de búsqueda no informadas. En nuestro ejemplo, y para este último caso, podemos imaginar un robot que no posea ningún tipo de visión artificial, que únicamente sea capaz de moverse en horizontal o vertical de un baldosín a otro y detectar si en el baldosín se halla el libro.

De esta forma, los algoritmos de búsqueda pueden ser:

Consiste en ir comparando el elemento a buscar con cada elemento del vector hasta encontrarlo o hasta que se llegue al final, esto hace que la búsqueda sea secuencialmente (de ahí su nombre). La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del vector. Se utiliza sin importar si el vector está previamente ordenado o no. A continuación se muestra el pseudocódigo del algoritmo:^[1]​

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias. En el peor de los casos el número máximo de comparaciones es ${ extstyle lfloor log _{2}n+1 floor }$, donde ${displaystyle n}$ es el número de los elementos en el vector. Por ejemplo, en uno conteniendo 50.000.000 elementos, el algoritmo realiza como máximo 26 comparaciones.

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del vector (normalmente el elemento central): si el valor de este es mayor que el del elemento buscado se repite el procedimiento en la parte del vector que va desde el inicio de este hasta el elemento tomado, en caso contrario se toma la parte del vector que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el vector.

A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del vector.