 |
 |
5.6)Búsqueda en vectores.A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arrays. Pudiera ser necesario determinar si un vector contiene un valor determinado que coincide con algún valor clave o buscado. El proceso de encontrar en un array un elemento particular, se llama búsqueda.
Una operación de búsqueda de un dato en un vector consiste en:
- Determinar si el dato pertenece o no al vector.Dos de los métodos más usuales de búsqueda en vectores son:- En caso de pertenecer , determinar cuál es su posición.
- Busqueda secuencial o lineal.La búsqueda secuencial consiste en recorrer secuencialmente un array desde el primer elemento hasta el último y comprobar si alguno de los elementos del array contiene el vector buscado, es decir, comparar cada elemento del array con el valor buscado. Dado que el array no está en ningún orden particular, existe la misma probabilidad de que el valor se encuentre, ya sea en el primer elemento como en el último. Por tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.- Busqueda binaria.
La búsqueda secuencial requiere, para el peor de los casos, cuando el elemento a buscar es el último o no se encuentra, recorrer todo el vector y realizar un número de comparaciones igual al tamaño del vector, de lo que deducimos que para vectores con muchos elementos esta búsqueda puede no ser conveniente.
El método de búsqueda lineal funciona bien para arrays pequeños o para arrays no ordenados. Si el array está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria.
La búsqueda binaria de un valor en un vector consiste en analizar, en primer lugar el elemento central del vector, si el elemento buscado es menor se buscar por el tramo inferior del vector utilizando la misma técnica, y si no por el tramo superior. Es decir, después de cada una de las comparaciones elimina la mitad de los elementos en el arreglo bajo búsqueda. En la segunda iteración el tramo a buscar es la mitad (bien derecha, bien izquierda) del vector y el elemento a evaluar es el central de este nuevo tramo. Esto supone claramente que el vector ha debido ser ordenado previamente.
La búsqueda binaria requiere menos iteraciones, comparaciones, que la búsqueda secuencial pero para realizar la búsqueda se requiere que el vector esté previamente ordenado.
Veamos un ejemplo de cómo se realiza una búsqueda binaria sobre un vector de enteros ordenados en orden creciente:
La busqueda binaria difiere de la búsqueda secuencial en el tiempo que tarda en ejecutarse. Para poder determinar cuál de los dos métodos es más rápido, es decir, cuál es el primero en encontrar el elemento en el peor de los casos, se deberá establecer una unidad de medida "teórica" que, a partir de las instrucciones, pueda establecer una comparación entre los algoritmos.Para ello la complejidad temporal o coste de un programa se mide por el número de iteraciones que realizan los bucles de ese programa. Si aparecen varios bucles independientes dentro del programa, la complejidad temporal sería la suma de sus iteraciones.