Algoritmos de búsqueda
Los algoritmos de búsqueda son aquellos que se centran en buscar un cierto elemento dentro de un vector y, quizá, devolver la posición en la que se encuentra dicho elemento. Vamos a estudiar dos algoritmos: el algoritmo básico de búsqueda (búsqueda secuencial), y el algoritmo de búsqueda dicotómica. Este último es más rápido que el primero, pero como contrapartida tiene que sólo funcionará cuando el vector en el que se busca está ordenado. Si el vector no está ordenado, no tiene ningún sentido hacer una búsqueda dicotómica.
Algoritmo de búsqueda secuencial
Es muy sencillo: se trata de recorrer el vector, elemento por elemento, preguntando si el elemento que visitamos es igual al que estamos buscando, y terminando de buscar cuando lo encontremos. El algoritmo quedaría como sigue (nuevamente, suponemos que tratamos con un vector de enteros):
VARIABLES
encontrado: Logico;
v: Vector[1..N] de Entero;
i, elemBuscado: Entero:
FIN VARIABLES
Leer_del_teclado(elemBuscado);
encontrado = Falso;
i = 1;
mientras NO(encontrado) Y (i < N) hacer
si v[i] = elemBuscado entonces
encontrado = Verdadero;
fin si
i = i + 1;
fin mientras
Es evidente que si al terminar de recorrer el vector, tenemos que encontrado=Falso, quiere decir que no se ha encontrado el elemento dentro del vector.
Algoritmo de búsqueda dicotómica
Como ya hemos dicho, este algoritmo asume que estamos trabajando con un vector ordenado. Esta asunción no es a la ligera, y no debemos olvidarla, como comprobaremos a continuación.
La idea es empezar a buscar el elemento objetivo por la mitad del vector, es decir, miraremos si el elemento que está en el centro del vector coincide con el elemento buscado. Si coincide, ya hemos terminado. Si no coincide, entonces miramos qué sucede: si el elemento buscado es menor que el elemento que está en el centro del vector, entonces sólo buscaremos en el subvector izquierdo; si el elemento buscado es mayor que el que está en el centro del vector, entonces sólo buscaremos en el subvector derecho. Se entiende por subvector izquierdo el vector formado por los elementos [1..centro - 1] y por subvector derecho el vector formado por los elementos [centro + 1..N].
Dentro del subvector adecuado, repetimos el proceso: comparamos con el elemento central. Si es igual, hemos terminado, si es menor, buscamos en el subvector izquierdo, si es mayor, buscamos en el subvector derecho.
La manera de colocarnos en el subvector adecuado es por medio de tres variables auxiliares, que llamaremos izq, der y medio. En la variable izq almacenaremos la posición del vector que se corresponderá con el extremo izquierdo del subvector, en la variable der almacenaremos la posición del vector que se corresponderá con el extremos derecho del subvector, y en la variable medio almacenaremos la posición central del subvector.
Por ejemplo, si tenemos el vector [1, 2, 3, 4, 5], empieza siendo izq = 1, der = 5 y medio = 3. Ahora bien, el subvector izquierdo correspondería a izq = 1, der = 2 (= medio - 1), mientras que el subvector derecho correspondería a izq = 4 (= medio + 1), der = 5.
Es decir, si nos toca movernos al subvector izquierdo, ajustaremos el valor de der como der = medio - 1 dejando izq como está, mientras que si nos toca movernos al subvector derecho, ajustaremos el valor de izq como izq = medio + 1, dejando der como está. En ambos casos hay que recalcular medio = (izq + der)/2, ya que al movernos a cualquiera de los dos subvectores, la posición central cambia.
Vamos a estudiarlo con detenimiento en el siguiente ejemplo. Buscamos si el valor 12 está en el siguiente vector:
v = [1, 2, 3, 4, 12, 13, 14]
El vector tiene N = 7 elementos, izq = 1, der = 7, medio = (izq + der) / 2 = (1+7)/2 = 4. Así que empezamos viendo si v[medio] = 12. Pero v[4] = 4, que no es 12. Ahora bien, ¿12 < 4? No, entonces no buscamos en el subvector izquierdo (que sería [1, 2, 3]). Si 12 <> 4 y no es 12 < 4, tiene que ser 12 > 4, así que buscamos en el subvector derecho: [12, 13, 14]. Esto requiere que ajustemos los valores de izq, der y medio.
Como nos hemos movido al subvector derecho, izq = medio + 1 = 5, der = 7, y ahora medio = (izq + der)/2 = (5+7)/2 = 6 (observamos que la posición 6 del vector se corresponde con el centro del subvector [12, 13, 14]). Así que vemos si v[6] = 12. Pero v[6] = 13, que no es 12. ¿12 < 13? Sí, pues entonces buscamos en el subvector izquierdo, que es [12].
Tenemos que ajustar de nuevo los valores de izq, der y medio. Como nos hemos movido al subvector izquierdo, izq se queda como está (izq = 5), der = medio - 1 = 6-1 = 5, medio = (izq + der)/2 = (5+5)/2 = 5. Así que vemos si v[5] = 12. Efectivamente, v[5] = 12, que es el valor buscado.
Gráficamente (para intentar aclarar un poco más):
Ahora bien, ¿cómo sabemos si un elemento no está dentro del vector utilizando este algoritmo? Lo sabremos en el momento en que izq > der. Cuando se crucen los valores de izq y der es porque no se ha encontrado el elemento. Vamos a ver cómo sería el algoritmo:
VARIABLES
v: Vector[1..N] de Entero;
encontrado: Logico;
izq, der, medio, elemBuscado: Entero;
FIN VARIABLES
Leer_del_teclado(elemBuscado);
encontrado = Falso;
izq = 1;
der = n;
mientras (izq < der) Y NO(encontrado) hacer
medio = (izq + der) / 2;
si v[medio] = elemBuscado entonces
encontrado = Verdadero;
sino
si v[medio] < elemBuscado entonces
izq = medio + 1;
sino (* v[medio] > elemBuscado *)
der = medio - 1;
fin si
fin si
fin mientras
Tutoriales
