10. Algoritmia, Esquema búsquedaEsquema de búsqueda en una secuencia

El segundo esquema de tratamiento secuencial es el de búsqueda. Te permitirá buscar un elemento concreto dentro de una secuencia.

A diferencia del esquema de recorrido de una secuencia, en el cual, se recorría toda la secuencia siempre, en este esquema, se recorre la secuencia hasta encontrar el elemento que cumpla con una condición determinada.

Concepto de secuencia, cabezal y posición extra

La secuencia es el número de elementos que tenemos que tratar o comprovar.

El cabezal representa hacía qué elemento apunta o está tratando el algoritmo en cada una de las iteraciones.

La posición extra es cuando el cabezal está situado más allá de los elementos a tratar de la secuencia. En la imagen de abajo, la posición extra sería el número 9, la secuencia es del 1 al 8.

Plantilla del esquema de búsqueda

Primero te presento el esquema o plantilla del esquema de búsqueda, que deberás ir refinando en los pasos siguientes.

algoritmo esquemaBusqueda
   var
      encontrado: booleano;
   fvar
   
   preparar secuencia
      encontrado := falso;
   inicio tratamiento
   {cabezal está al principio de la secuencia,
    todavía no se ha tratado ningún elemento}

   mientras no fin secuencia y no encontrado hacer
      {tratado la parte izquierda del cabezal. El
      elemento buscado no está en esta parte de la
      secuencia y elcabezal no está en la posición
      extra final}
      actualizar encontrado
      si no encontrado entonces
         tratar elemento
         avanzar secuencia
      fsi
      {tratado la parte izquierda secuencia,
      el elemento buscado no está en esta parte
      de la secuencia. Si encontrado es cierto,
      se ha encontrado el elemento buscado}
   fmientras
   {secuencia tratada. cabezal final secuencia.
   El elemento buscado no está en esta parte de la
   secuencia. Si encontrado es cierto, el cabezal
   apunta al elemento buscado. Y si es falso, el
   cabezal estará en el final de la secuencia}
   tratamiento final
falgoritmo

Este esquema está preparado para el caso que la secuencia recorrida no contenga el elemento buscado. En ese caso, la variable encontrado seguirá valiendo falso. En cada iteración, el condicional hace avanzar la secuencia y realizar cálculos según convenga.

Si la secuencia contiene el elemento buscado, el algoritmo no entra en el condicional, ya que la variable encontrado es cierta, por lo que no se actualiza el cabezal.

En la siguiente iteración, como ya no se cumple la condición…mientras no fin secuencia y no encontrado hacer se sale del bucle y el tratamiento final se aplica al elemento deseado.

Refinamiento del esquema

Ahora toca adaptar la plantilla a nuestras necesidades. Para ilustrar este esquema desarrollaremos un algoritmo que determine si un número es primo.

El algoritmo debe retornar cierto si sí lo es y falso en caso contrario. Si te fijas, vamos a desarrollar una función que realice esta «sencilla tarea» que después puedes reutilizar en cualquier programa para realizar tareas más complejas que necesiten comprobar si un número es primo.

Nota: Recuerda que un número es primo cuando tiene exactamente dos divisores; el 1 y él mismo. Por lo tanto, el número 1 no se considera primo porque sólo tiene un divisor.

Aquí te muestro la función, para después razonarla:

funcion esPrimo(n:entero): booleano
   {Pre: n > 0}
   var
      encontrado, primo: booleano;
      i: entero;
   fvar
   i:=2; // preparar secuencia
   encontrado := falso;
   mientras i < n y no encontrado hacer // fin secuencia
      si n mod i = 0 entonces
         encontrado := cierto; // actualizar encontrado
      fsi
      si no encontrado entonces
         i := i + 1; // avanzar secuencia
      fsi
   fmientras
   primo := no encontrado;
   retorna primo;
   {Post: primo es cierto si n es primo y
    falso en caso contrario}
ffuncion

Preparación de secuencia

Como tenemos que recorrer la secuencia de número entre 1 y el número que queremos comprobar si es primo, la secuencia siempre empezará en 2, ya que como hemos dicho 1 no es primo y cualquier número es divisible entre 1. Por lo tanto, la preparación de la secuencia en este caso consiste en inicializar una variable a 2. La he llamado i.

i := 2;

Inicio tratamiento

En este caso concreto no hay tratamiento inicial.

Fin del tratamiento secuencia

El final de la secuencia corresponde cuando la variable i sea mayor o igual que n, es decir el número que hay que comprobar si es primo.

Nota: Observa que si queremos saber si el número 2 es primo, no llega a entrar en el bucle mientras, ya que la condición de fin de secuencia es i<n y 2<2 es falsa, por lo tanto daría un falso negativo. Pero, la última instrucción antes de devolver el valor niega la variable primo, por lo tanto salvamos la situación.

Actualizar variable encontrado

Si hacemos el módulo entre el número n y un número entre 1 y el número n-1 (sin contar estos dos) y como resultado da 0, quiere decir que es divisible. Por lo tanto ese número no es primo. En este caso hay que actualizar la variable encontrado al valor cierto, para que en la próxima iteración salga del bucle.

encontrado := cierto;

Avanzar secuencia

Aquí sencillamente incrementamos en 1 la variable i.

i := i + 1;

Tratamiento final

El retorno más lógico de esta función sería devolver falso si el número no es primo y cierto si sí lo es. Pero he planteado el problema de la forma que cuando encuentra un divisor la variable encontrado pasa a cierto (no es primo) y cuando no encuentra un divisor la varaible encontrado es falso ( es primo). Por eso en el tratamieno final tenemos que negar el resultado de la variable primo.

primo := no encontrado;

Metodología

Como te indiqué en la anterior entrada sobre el esquema de recorrido de una secuencia, en el último apartado, es muy importante seguir la misma metodología. Es una forma de centrase en el problema y no dejarse aspectos críticos, como bucles infinitos o que dejes valores de la secuencia sin contemplar.

Si te ha gustado o te ha aclarado conceptos el contenido de este artículo compártelo en redes sociales para que pueda crecer, ¡Muchas gracias!