4.3 Problemas de recorrido, búsqueda y ordenación

Muchos de los problemas que se plantean cuando se utilizan arrays pueden clasificarse en tres grandes grupos de problemas genéricos:

a) los que conllevan el recorrido de un array,

b) los que suponen la búsqueda de un elemento que cumpla cierta característica dentro del array, y

c) los que implican la ordenación de los elementos del array.

La importancia de este tipo de problemas proviene de que surgen, no sólo en el ámbito de los arrays, sino también en muchas otras organizaciones de datos de uso frecuente (como las listas, los ficheros, etc.). Las estrategias básicas de resolución que se verán a continuación son también extrapolables a esos otros ámbitos.

a) Problemas de recorrido¶

Se clasifican como problemas de recorrido aquellos que para su resolución exigen algún tratamiento de todos elementos del array. El orden para el tratamiento de estos elementos puede organizarse de muchas maneras: ascendentemente, descendentemente, ascendente y descendente de forma simultánea, etc.

Ejemplo de recorrido

A partir de un array que contiene la pluviosidad de cada uno de los días de un mes, realizar un método que calcule la pluviosidad media de dicho mes. Para ello se recorren ascendente los componentes del array para ir sumándolos:

public static double pluviosidadMediaAscendente(double lluvia[]){
    double suma = 0;

    //Recorremos el array
    for (int i = 0; i<lluvia.length; i++) {
        suma += lluvia[i];
    }
    double media = suma / lluvia.length;

    return media;
}

La forma de recorrer el array ascendentemente es, como vemos, utilizar una variable entera (i en nuestro caso) que actúa como subíndice del array. Éste subíndice va tomando los valores 0, 1, ..., lluvia.length-1 en el seno de un bucle, de manera que se accede a todos los componentes del array para sumarlos.

Ejemplo de recorrido descendente

El mismo problema resuelto con un recorrido descendente sería como sigue:

public static double pluviosidadMediaDescendente(double lluvia[]){
    double suma = 0;

    //Recorremos el array
    for (int i = lluvia.length-1; i>=0; i--) {
        suma += lluvia[i];
    }
    double media = suma / lluvia.length;

    return media;
}

Ejemplo 2 de recorrido

También realizamos un recorrido para obtener la pluviosidad máxima del mes (la cantidad de lluvia más grande caída en un día), es decir, el elemento más grande del array:

public static double pluviosidadMaxima(double[] lluvia){
    // Suponemos el la pluviosidad máxima se produjo el primer día
    double max = lluvia[0];

    //Recorremos el array desde la posición 1, comprobando si hay una pluviosidad mayor
    for (int i = 1; i<lluvia.length; i++) {
        if(lluvia[i] > max) max = lluvia[i];
    }

    return max;
}

b) Problemas de búsqueda¶

Se denominan problemas de búsqueda a aquellos que, de alguna manera, implican determinar si existe algún elemento del array que cumpla una propiedad dada. Con respecto a los problemas de recorrido presentan la diferencia de que no es siempre necesario tratar todos los elementos del array: el elemento buscado puede encontrarse inmediatamente, encontrarse tras haber recorrido todo el array, o incluso no encontrarse.

Búsqueda ascendente¶

En este tipo de búsqueda se inicia esta en el elemento cero y vamos ascendiendo hasta la última posición del array.

Ejemplo de búsqueda ascendente

Problema de encontrar cual fue el primer día del mes en que no llovió nada, es decir, el primer elemento del array con valor cero:

// Devolveremos el subíndice del primer componente del array cuyo valor es cero.
// Si no hay ningún día sin lluvias devolveremos -1
public static int primerDiaSinLluvia1(double lluvia[]){
    int i=0 ;
    boolean encontrado = false ;

    while (i<lluvia.length && !encontrado){
        if (lluvia[i] == 0) {
            encontrado = true ;
        } else {
            i++ ;
        }
    }
    if (encontrado) {
        return i ;
    } else {
        return -1 ;
    }
}

Hemos utilizado el esquema de búsqueda: Definimos una variable boolean que indica si hemos encontrado o no lo que buscamos. El bucle se repite mientras no lleguemos al final del array y no hayamos encontrado un día sin lluvias.

Ejemplo de búsqueda

También es posible una solución sin utilizar la variable boolean:

public static int primerDiaSinLluvia2(double lluvia[]){
    int i=0 ;

    while (i<lluvia.length && lluvia[i] != 0){
        i++;
    }
    if (i == lluvia.length) {
        return -1 ;
    } else {
        return i;
    }
}

En este caso el subíndice i se incrementa mientras estemos dentro de los límites del array y no encontremos un día con lluvia 0. Al finalizar el bucle hay que comprobar por cuál de las dos razones finalizó: ¿Se encontró un día sin lluvias o se recorrió todo el array sin encontrar ninguno? En esta comprobación es importante no acceder al array si existe la posibilidad de que el subíndice esté fuera de los límites del array.

La siguiente comprobación sería incorrecta ya que, si se ha finalizado el bucle sin encontrar ningún día sin lluvia, i valdrá lluvia.length, que no es una posición válida del array, y al acceder a lluvia[i] se producirá la excepción ArrayIndexOutOfBoundsException (índice del array fuera de los límites).

if (lluvia[i] == 0) {
    return i;
} else {
    return -1;
}

Por otra parte, el mismo problema se puede resolver utilizando la sentencia for, como hemos hecho otras veces. Sin embargo la solución parece menos intuitiva porque el cuerpo del for quedaría vacío:

public static int primerDiaSinLluvia3(double lluvia[]){
    int i;

    for (i=0; i<lluvia.length && lluvia[i] != 0; i++);  /*Nada*/

    if (i == lluvia.length) {
        return -1 ;
    } else {
        return i;
    }
}

Búsqueda descendente¶

Si queremos encontrar el último día del mes en que no llovió podemos realizar una búsqueda descendente, es decir, partiendo del último componente del array y decrementando progresivamente el subíndice hasta llegar a la posición cero o hasta encontrar lo buscado:

public static int ultimoDiaSinLluvia(double lluvia[]){
    int i=lluvia.length-1;
    boolean encontrado = false ;

    while (i>=0 && !encontrado){
        if (lluvia[i] == 0) {
            encontrado = true ;
        } else {
            i-- ;
        }
    }

    if (encontrado) {
        return i ;
    } else {
        return -1 ;
    }
}

Búsqueda en un array ordenado: búsqueda binaria¶

Supuesto

Vamos a suponer, por ejemplo, que una amiga apunta un número entre el 0 y el 99 en una hoja de papel y vosotros debéis adivinarlo. Cada vez que conteste, le dirá si el valor que ha dicho es mayor o menor que el que debemos de adivinar. ¿Qué estrategia seguirías para lograrlo? Hay que pensar un algoritmo a seguir para resolver este problema.

Una aproximación muy ingenua podría ser ir diciendo todos los valores uno por uno, empezando por 0. Está claro que cuando llegue al 99 lo habréis adivinado. En el mejor caso, si había escrito el 0, acertará en la primera, mientras que en el peor caso, si había escrito el 99, necesitaréis 100 intentos. Si estaba por medio, tal vez con 40-70 basta. Este sería un algoritmo eficaz (hace lo que tiene que hacer), pero no muy eficiente (lo hace de la mejor manera posible). Ir probando valores al azar en lugar de hacer esto tampoco mejora gran cosa el proceso, y viene a ser lo mismo.

Si alguna vez habéis jugado a este juego, lo que habréis hecho es ser un poco más astutos y empezar por algún valor del medio. En este caso, por ejemplo, podría ser el 50. Entonces, en caso de fallar, una vez estás seguro de si el valor secreto es mayor o menor que tu respuesta, en el intento siguiente probar un valor más alto o más bajo , e ir haciendo esto repetidas veces.

Generalmente, la mejor estrategia para adivinar un número secreto entre 0 y N sería primer probar N/2. Si no se ha acertado, entonces si el número secreto es más alto se intenta adivinar entre (N/2 + 1) y N. Si era más bajo, se intenta adivinar el valor entre 0 y N-1. Para cada caso, se vuelve a probar el valor que hay en el medio del nuevo intervalo. Y así sucesivamente, haciendo cada vez más pequeño el intervalo de búsqueda, hasta adivinarlo. En el caso de 100 valores, esto garantiza que, en el peor de los casos, en 7 intentos seguro que se adivina. Esto es una mejora muy grande respecto al primer algoritmo, donde hacían falta 100 intentos, y por tanto, este sería un algoritmo más eficiente. Concretamente, siempre se adivinará en log₂ (N) intentos como máximo.

Si os fijáis, el supuesto que se acaba de explicar, en realidad, no es más que un esquema de búsqueda en una secuencia de valores, como puede ser dentro de un array, partiendo de la condición que todos los elementos estén ordenados de menor a mayor. De hecho, hasta ahora, para hacer una búsqueda de un valor dentro de un array se ha usado el sistema "ingenuo", mirando una por una todas las posiciones. Pero si los elementos están ordenados previamente, se podría usar el sistema "astuto" para diseñar un algoritmo mucho más eficiente, y hasta cierto punto, más "inteligente".

El algoritmo basado en esta estrategia se conoce como búsqueda binaria o dicotómica.

Para ello iniciaremos la búsqueda en la posición central del array.

Si el elemento central es el buscado habremos finalizado la búsqueda.
Si el elemento central es mayor que el buscado, tendremos que continuar la búsqueda en la mitad izquierda del array ya que, al estar éste ordenado todos los elementos de la mitad derecha serán también mayores que el buscado.
Si el elemento central es menor que el buscado, tendremos que continuar la búsqueda en la mitad derecha del array ya que, al estar éste ordenado todos los elementos de la mitad izquierda serán también menores que el buscado.

En un solo paso hemos descartado la mitad de los elementos del array. Para buscar en la mitad izquierda o en la mitad derecha utilizaremos el mismo criterio, es decir, iniciaremos la búsqueda en el elemento central de dicha mitad, y así sucesivamente hasta encontrar lo buscado o hasta que descubramos que no está.

Supongamos por ejemplo que, dado un array que contiene edades de personas, ordenadas de menor a mayor queremos averiguar si hay alguna persona de 36 años o no.

El siguiente método soluciona este problema realizando una búsqueda binaria:

public static boolean hayAlguienDe36(int edad[]) {
    // Las variables izq y der marcarán el fragmento del array en el que
    // realizamos la búsqueda. Inicialmente buscamos en todo el array.
    int izq = 0;
    int der = edad.length - 1;
    boolean encontrado = false;

    while (izq <= der && !encontrado) {
        // Calculamos posición central del fragmento en el que buscamos
        int m = (izq + der) / 2;
        if (edad[m] == 36) {   
            // Hemos encontrado una persona de 36
            encontrado = true;
        } else if (edad[m] > 36) {
            // El elemento central tiene más de 36.
            // Continuamos la búsqueda en la mitad izquierda. Es decir,
            // entre las posiciónes izq y m-1
            der = m - 1;
        } else {
            // El elemento central tiene menos de 36.
            // Continuamos la búsqueda en la mitad derecha. Es decir,
            // entre las posiciones m+1 y der
            izq = m + 1;
        } // fin del if
    } // fin del while

    return encontrado; // if (encontrado) return true; else return false;
}

La búsqueda finaliza cuando encontramos una persona con 36 años (encontrado==true) o cuando ya no es posible encontrarla, circunstancia que se produce cuando izq y der se cruzan (izq>der).

c) Problemas de ordenación¶

Con frecuencia necesitamos que los elementos de un array estén ordenados.

Existen multitud de algoritmos que permiten ordenar los elementos de un array, entre los que hay soluciones iterativas y soluciones recursivas.

Entre los algoritmos iterativos tenemos, por ejemplo, el método de la burbuja, el método de selección directa y el método de inserción directa.
Entre los recursivos, son conocidos el algoritmo mergeSort y el quickSort, que realizan la ordenación más rápidamente que los algoritmos iterativos que hemos nombrado.

Como ejemplo vamos a ver cómo se realiza la ordenación de un array de enteros utilizando el método de selección directa:

public static void seleccionDirecta(int v[]) {

    for (int i = 0; i < v.length-1; i++) {
        // Localizamos elemento que tiene que ir en la posición i
        int posMin = i;
        // Buscar el menor a la derecha
        for (int j = i + 1; j < v.length; j++) {
            if (v[j] < v[posMin]) {
                posMin = j;
            }
        }
        // Al llegar aquí posMin tendrá la posición del elemento menor
        // Intercambiamos los elementos de las posiciones i y posMin
        // v[i]<=>v[posMin];
        int aux = v[posMin];
        v[posMin] = v[i];
        v[i] = aux;
    }
}

El método consiste en recorrer el array ascendentemente a partir de la posición cero.

En cada posición (i) localizamos el elemento que tiene que ocupar dicha posición cuando el array esté ordenado, es decir, el menor de los elementos que quedan a su derecha.

Cuando se ha determinado el menor se coloca en su posición realizando un intercambio con el elemento de la posición i. Con ello, el array queda ordenado hasta la posición i.

Ejemplos visuales de ordenación

Ejemplos visuales de distintos métodos de ordenación, con distintos tipos de entradas: https://www.toptal.com/developers/sorting-algorithms.

Bucle for each (for-loop)¶

En el tema anterior vimos algún tipo de bucles que explicaríamos cuando los pudiésemos utilizar, en este grupo están los bucles for each o for-loops. Aquí tenemos un ejemplo de recorrido de un array con la sintaxis que ya conocemos:

forfor each

Un ejemplo para recorrer un array mediante un for:

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
}

El anterior fragmento genera la siguiente salida:

1	`1 2 3 4 5 6 7 8`

Este mismo código se puede escribir mediante un for each de la siguiente manera:

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
for (int i : array) { 
    // mentalmente podemos traducir por:
    // "para cada entero "i" que encontremos en el array"
    System.out.print(i + " ");
}

La salida seguirá siendo la misma:

1	`1 2 3 4 5 6 7 8`

Cuidado con el segundo método

Con el segundo método no tenemos acceso a la posición o índice del array, este método no serviría para métodos en los que necesitamos conocer la posición o utilizarla de alguna manera.

Ejemplo completo de método de búsqueda binaria

Enlace a ejercicio completo del método de búsqueda binaria.