|
 El algoritmo de búsqueda lineal es uno de los más utilizados en situaciones bastante comunes. Es también uno de los algoritmos más sencillos e intuitivos.
Sin embargo, resulta curioso comprobar cómo en gran cantidad de aplicaciones, muchas de ellas de ámbito altamente «profesional» se perpetran extrañas implementaciones que en algunos casos conllevan manifiestas ineficiencias y en otros peligros de salirse de los límites de los datos, por no hablar de situaciones en las que la programación estructurada se deja de lado.
En éste artículo vamos a reflexionar acerca de la búsqueda lineal y de sus posibles implementaciones defendiendo la bondad o no de cada una de ellas.
El escenario en el que se aplica el algoritmo es simple: tenemos una estructura de datos que es posible recorrer secuencialmente (aunque pueda ser recorrida de otra forma, por ejemplo, aleatoriamente, para este algoritmo basta con que se pueda hacer secuencialmente) y queremos saber si alguno de los datos de la estructura cumple algun predicado, y/o en qué posición está ese dato. Si hubiesen varios datos que lo cumplen, basta con encontrar el primer dato que cumple dicho predicado. En este contexto, utilizamos predicado como una cualidad o condición del dato que sea comprobable mediante una expresión lógica booleana... es decir... que se pueda evaluar a verdadero o a falso para un determinado dato.
Esa formulación básica puede ser asimilada a otras muchas situaciones... una vez encontrado un algoritmo de búsqueda lineal genérico veremos que la misma estructura puede ser adaptada a otros problemas de búsqueda... pero ya hablaremos de ello en otros artículos.
Como hay que empezar por algún sitio, en éste artículo lo haremos razonando sobre un supuesto básico: saber si un elemento se encuentra en un array unidimensional, y si es así, conocer su posición.
Supongamos un array de enteros llamado A y un entero llamado x. Construiremos un método tal que dado el array A y el entero x nos diga si hay algún elemento en A cuyo valor sea x, y si es así, su posición.
La cabecera del método (ilustrado en C#, como de costumbre) debería ser algo así como
int BuscaPosicion(int[] A, int x)
{
...
}
Si hay algún entero en A que sea igual a x, nos devolverá su posición. Si no hay ninguno, utilizaremos el viejo truco de indicarlo devolviendo un "-1". Como las posiciones del array son números mayores o iguales a 0 y el tipo de retorno del método es un int, utilizamos un negativo (el -1) que es un valor que como posición del array no tiene sentido, para indicar que no se ha encontrado.
Una de las implemetaciones que se ven a menudo es la que sigue a continuación. Es muy común, sin embargo, muy ineficiente. En ella, se utiliza un bucle for, para recorrer todos los elementos del array, y una variable llamada posicion que va a contener la posición en la que se ha encontrado un elemento de A que es igual a x. Como inicialmente, cuando el algoritmo comienza, no se ha encontrado ningún elemento, se inicializa esa variable a "-1" directamente. A medida que avanza el bucle for, si encontramos un elemento que sea igual a x, cambiamos el valor de la variable posición.
int BuscaPosicion(int[] A, int x)
//OJO: ESTA IMPLEMENTACION NO ES MUY BUENA
{
//empezamos suponiendo que no lo
//hemos encontrado
int posicion = -1;
for (int i = 0; i < A.Length; i++)
{
if (A[i] == x)
{
posicion = i;
}
}
return posicion;
}
Parece que funciona ¿no?.... ¡Pues no! Ni funciona tiene un planteamiento razonable.
Imagina que en un despiste no sé donde he dejado las llaves de casa... entonces, planeo utilizar la siguiente estrategia de búsqueda: voy a buscar en el salón, en el dormitorio, en la cocina y en el cuarto de baño, por ese orden... resulta que me las había dejado en el dormitorio ¿sigo buscando en la cocina y en el cuarto de baño? No ¿verdad?. Pues eso es lo que hace este algoritmo. Si el array tiene 1000 posiciones y encuentro x en la 3ª, con el bucle for se siguen revisando las restantes 997... Pero no solo eso... Hemos quedado que en la búsqueda secuencial, me basta con saber la primera posición en la que se cumple el predicado. Si x vuelve a encontrarse en la posición 900, éste algoritmo devolvera 900, cuando realmente debería haber devuelto un 3... Así pues, ni es eficiente ni hace lo que debe.
Vale... A ver si lo podemos arreglar.
int BuscaPosicion(int[] A, int x)
{
//OJO: ESTA IMPLEMENTACION NO ES MUY BUENA
//empezamos suponiendo que no lo
//hemos encontrado
int posicion = -1;
for (int i = 0; i < A.Length; i++)
{
if (A[i] == x)
{
posicion=i;
break; //MIRA AQUÍ
}
}
return posicion;
}
Vale hemos hecho un apaño. Mira en el interior del if. Ahora, en cuanto encontramos un valor en A que es igual a x interrumpimos el bucle. Bueno, éste sí que funciona y no es ineficiente, ya que termina en el momento en el que se encuentra lo que buscamos, pero es criticable desde el punto de vista de la corrección formal. Introducir una instrucción break para interrumpir un bucle for supone una ruptura del flujo lineal, equivalente a la introducción de un salto incondicional ("goto"). El bucle for no fue ideado para ser interrumpido. El hecho de que algunos lenguajes lo permitan no significa que dicha interrupción deba ser recurso frecuente de un programador. La programación estructurada fue un gran logro en el campo de la informática hace más de 30 años, y una ruptura en el flujo de una estructura iterativa como el for supone no estar utilizando programación estructurada, con las consecuencias que ello conlleva. Sin duda, ésta no es una estrategia acertada. Cuando un programador ve un bucle for hecho por otro programador, espera que el bucle termine de manera natural... es decir, cuando su índice ha tomado ya todos los valores del rango en el que se define el bucle.
A ver si lo logramos a la tercera.
int BuscaPosicion(int[] A, int x)
{
//OJO: ESTA IMPLEMENTACION NO ES MUY BUENA
//empezamos suponiendo que no lo
//hemos encontrado
int posicion = -1;
for (int i = 0; i < A.Length; i++)
{
if (A[i] == x)
{
return i; //MIRA AQUÍ
}
}
return posicion;
}
Pues va a ser que no. En esta ocasión estamos igual que antes. En el interior del if hemos colocado un hábil return que hará que el método termine en cuanto se encuentre x... pero estamos en las mismas... Supone interrumpir un bucle, y por lo tanto, una ruptura en el flujo de ejecución de la estructura for. Nuevamente, no estamos utilizando programación estructurada, al poner dos puntos de salida en el mismo método.
Bueno... Y ¿qué conclusiones debemos sacar de estos tres fracasos? ¡Pues que nos estamos equivocando de bucle!
Consideremos otros bucles... por ejemplo, el do-while (o repeat-until, en lenguajes derivados del Pascal). La característica clave de éste bucle es que se repite al menos una vez. Bien... si me pasan un array A totalmente vacío, es decir, con 0 elementos no tendía sentido utilizar una estructura iterativa que exige hacer cosas al menos una vez. Ese escenario no solo es posible, sino bastante frecuente. Por ejemplo, muchos problemas empiezan con arrays completamente vacíos que se van llenando a medida que la aplicación que los resuelve avanza. Así pues, queda descartado el bucle do-while.
A estas alturas parece evidente que el candidato ideal es el bucle while.
Veamos esta implementación.
int BuscaPosicion(int[] A, int x)
{
//OJO: ESTA IMPLEMENTACION NO ES MUY BUENA
//empezamos suponiendo que no lo
//hemos encontrado
int posicion = -1;
int i = 0;
//mientras el elemento
while ((A[i] != x) && (i < A.Length))
{
i++;
}
if (i < x)
{
posicion = i;
}
return posicion;
}
Nos vamos acercando. La implementación de arriba utiliza un bucle while que comprueba en su condición si hemos encontrado el elemento. Mientras no lo hayamos encontrado y el índice i esté dentro del rango, con la instrucción del interior del bucle incrementamos el índice para comprobar la posición siguiente en la siguiente iteración del bucle. No utiliza rupturas del flujo lineal (break, continue o goto) y no tiene nada más que un punto de salida (al final del método un solo return).
Si haces una traza, por ejemplo, con A={3,5,6,7,20,4,9} y x=7 verás que funciona perfectamente.
Sin embargo, si A es un array completamente vacío, nada más entrar a la función, la condición A[i]!=x intentará acceder a la posición i (que es 0), y sin embargo, la posición 0 no existe... por lo tanto esa implementación no es buena.
Lo curioso es que esta implementación es bastante común, y mucha gente no es consciente de la metedura de pata hasta que es tarde.
Es más, en algunas situaciones, si la condición del while se escribe de esta manera:
(i < A.Length) && (A[i] != x)
es incluso posible que funcione en algunas ocasiones debido a que nos salva la evaluación en cortocircuito. Pero no por ello la expresión deja de estar mal planteada ni desaparece la posibilidad de que dé problemas si no se aplica la evaluación en cortocircuito o se aplica empezando por el último término.
¿Lo arreglamos? A ver... Si no funciona para el caso de que A esté vacío, podemos comprobarlo antes. Metemos un if y arreglado:
int BuscaPosicion(int[] A, int x)
{
//OJO: ESTA IMPLEMENTACION NO ES MUY BUENA
//empezamos suponiendo que no lo
//hemos encontrado
int posicion = -1;
int i = 0;
if (A.Length > 0) //MIRA AQUÍ
{
while ((A[i] != x) && (i < A.Length))
{
i++;
}
if (i < x)
{
posicion = i;
}
}
return posicion;
}
¡Vaya chapuza!
Si la condición del while nos está dando problemas porque en un caso concreto no funciona bien (en el caso de que el array esté vacío) la solución más hábil no pasa por cascar un if que nos compruebe si es ese el caso. Mejor dedicar unos instantes a meditar acerca de si hemos colocado una condición sensata en el while.
De hecho, en general, no suele ser sensato acceder a posiciones de un array en la condición de un bucle while... ya sé que es tentador... pero antes de hacerlo hay que asegurarse de que siempre accedemos a posiciones del array válidas, aunque el array esté vacío.
Bueno... y entonces ¿cómo lo solucionamos? Muy fácil: accedamos al array siempre en el interior del bucle, y no en su condición. Podemos utilizar una variable booleana para saber si debemos entrar al bucle o no. Vamos a llamar a esa variable "encontrado". Inicialmente va a valer false. En la condición del bucle, evaluaremos dos cosas: que esa variable sea false y que el índice i esté dentro del rango del array. En el interior del bucle comprobamos si hemos encontrado x. Si es así, cambiamos la variable encontrado a true y eso hará que el bucle termine.
Después del bucle, si la variable encontrado está a true significa que el elemento está en el array, concretamente en la posición i-1.
Examina este código:
int BuscaPosicion(int[] A, int x)
{
//ESTA SOLUCIÓN ES MEJOR, PERO AUN PODEMOS
//AFINAR MÁS
//empezamos suponiendo que no lo
//hemos encontrado
int posicion = -1;
bool encontrado = false;
int i = 0;
//mientras no encontrado y el índice
//dentro del rango
while ((!encontrado) && (i < A.Length))
{
if (A[i] == x)
{
//esto hará que salgamos del bucle
encontrado = true;
}
i++;
}
//si lo hemos encontrado, la posición está en i-1
if (encontrado)
{
posicion = i-1;
};
return posicion;
}
Bueno... ese ya empieza a tener visos de cierta corrección: no tiene rupturas de flujo ni dos puntos de salida, y funcionará en todos los casos, incluso cuando el array esté vacío, sin necesidad de comprobarlo con un if.
Pero siguiendo con ese planteamiento, todavía podemos mejorarlo un poquito.
Realmente, no hace falta esa variable booleana. Sólo la hemos introducido para ilustrar el concepto de que cambiando un valor en el interior del bucle podemos salir de él sin necesidad de recurrir a otros subterfugios. De hecho, podemos utilizar el valor de la variable "posicion" en la condición del while. Alterando el valor de "posición" podremos salir del bucle.
 ¡Por fin hemos dado con una implementación del algoritmo relativamente buena!
int BuscaPosicion(int[] A, int x)
{
//empezamos suponiendo que no lo
//hemos encontrado
int posicion = -1;
int i = 0;
while ((posicion==-1) && (i < A.Length))
{
if (A[i] == x)
{
//con esta asignacion conseguimos
//salir del bucle y saber en qué
//posición está x
posicion = i;
}
else
{
//si no lo hemos encontrado pasamos a la
//posición siguiente
i++;
}
}
return posicion;
}
Esta última implementación es la mejor de todas las que hemos visto. En principio funcionará correctamente sea cual sea la longitud del array A (aunque sea 0) ya que sólo se accede al array en el interior del bucle, y no entraremos al bucle si la longitud del array es 0. El índice i está siempre dentro del rango, ya que cuando se llegue a la última posición también se sale del bucle.
Quizá te estés preguntando si la línea "i++;" podría ir fuera del "else". Pues sí: pero en ese caso, incrementaríamos i incluso cuando hemos encontrado x en A, cosa que no tiene la menor importancia pero no es realmente necesaria. |
Algoritmos 
