Lunes 24 de Mayo

Búsqueda en Arreglos

Objetivos: Mostrar patrones de programación que permiten resolver problemas típicos de búsqueda en arreglos.

Temas:

Búsqueda del mínimo/máximo

Un problema frecuente al trabajar con arreglos consiste en encontrar el mínimo/máximo valor en el arreglo. Por ejemplo, supongamos que el arreglo tabNotas contiene notas de alumnos en un control. Las llaves varían entre 1 y n. El siguiente programa encuentra el máximo y el mínimo:

    int i=1;
    double min= 7.1;
    double max= 0.0;
    while (i<=n) {
      double nota= tabNotas.getDouble(i);
      if (nota<min)
        min= nota;
      if (nota>max)
        max= nota;
      i= i+1;
    }
Observe que si el arreglo está vacío (n es 0), entonces al final del ciclo min es 7.1 y max es 0.0. Como estas notas no son válidas, se puede consultar por estos valores para determinar a posteriori que el arreglo estaba vacío.

Sin embargo, en el caso general no se conoce el rango que pueden tomar los valores en el arreglo. El siguiente patrón de programación se puede usar cuando se conoce que el arreglo tiene al menos un elemento:

    int llave= segunda llave;
    Tipo max= arreglo.getTipo(primera llave);
    while (llave<=última llave) {
      ...
      if (arreglo.getTipo(llave) > max)
         max= arreglo.getTipo(llave);
      ...
    }
No siempre lo único que se necesita es el valor del máximo. En ocasiones, también se necesita la posición del máximo en el arreglo (la llave):

    int llave= primera llave;
    Tipo max= arreglo.getTipo(primera llave);
    int llaveMax= primera llave;
    while (llave<=última llave) {
      ...
      if (arreglo.getTipo(llave) > max) {
         max= arreglo.getTipo(llave);
         llaveMax= llave;
      }
      ...
    }
Al final del ciclo, la variable llaveMax contiene la posición del máximo en el arreglo.

Búsqueda por contenido

Otro problema frecuente al trabajar con arreglos consiste en encontrar la llave cuyo valor asociado es un valor predeterminado. Por ejemplo, supongamos que el arreglo tabNombres contiene nombres (strings) de alumnos en un control. Las llaves varían entre 1 y n. El siguiente programa encuentra la llave i, tal que su valor asociado es nombre:

    String nombre= ...;
    int i=1;
    while (i<=n) {
      if (compare(tabNombres.getString(i),nombre)==0)
        break;
      i= i+1;
    }
    if (i<=n)
      ... // el nombre se encuentra en la posicion i
    else
      ... // el nombre no se encuentra en el arreglo
Esta búsqueda se escribe más elegantemente mediante:

    String nombre= ...;
    int i=1;
    while (i<n && compare(tabNombres.getString(i),nombre)!=0)
      i= i+1;
    if (i<=n)
      ... // el nombre se encuentra en la posicion i
    else
      ... // el nombre no se encuentra en el arreglo
Este último es un patrón muy utilizado en los problemas de búsqueda por contenido.

Ejercicio:

El arreglo tabNombres contiene nombres de alumnos, el arreglo tabNotas contiene sus notas en un control. Escriba un programa que entable el siguiente diálogo con el usuario:

    Nombre ? Gloria Hernandez
    Su nota es 6.0
    Nombre ? Juan Perez
    Su nota es 5.5
    Nombre ? Pablo Neruda
    No se encontro este alumno
    ...
    Nombre ? fin
    Fin.
Solución: la idea es utilizar el patrón anterior, pero colocándolo dentro de un ciclo de diálogo en donde en cada iteración se pregunta un nombre al usuario.

    while (true) {
      String nombre= readLine();
      if (compare(nombre, "fin")==0)
        break;
      int i=1;
      while (i<n && compare(tabNombres.getString(i),nombre)!=0)
        i= i+1;
      if (i<=n)
        println("Su nota es "+tabNotas.getDouble(i));
      else
        println("No se encontro este alumno");
    }
    println("Fin.");