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 las notas de n alumnos en un control(por lo tanto los índices van de 0 a n-1). El siguiente programa encuentra la mejor y la peor nota:

    int i=0;
    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:

    Tipo max= arreglo.getTipo(0);
    int k= 1;
    while (k<último índice) {
      ...
      if (arreglo.getTipo(k) > max)
         max= arreglo.getTipo(k);
      ...
    }
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 (el índice):

    Tipo max= arreglo.getTipo(0);
    int kMax= 0;
    int k= 1;
    while (k<último índice) {
      ...
      if (arreglo.getTipo(k) > max) {
         max= arreglo.getTipo(k);
         kMax= k;
      }
      ...
    }
Al final del ciclo, la variable kMax contiene la posición del máximo en el arreglo.

Búsqueda por contenido

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

    String nombre= ...;
    int i=0;
    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=0;
    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=0;
      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.");
(Ver el programa completo en Buscar.java.)