ESTRUCTURAS DE DATOS ESTÁTICAS Búsquedas en Arreglos

ESTRUCTURAS DE DATOS ESTÁTICAS Búsquedas en Arreglos

Descripción breve Explicaremos los métodos de búsqueda Secuencial, Secuencial Ordenado y Binaria, presentaremos los algoritmos en pseudocódigo y en lenguaje C, los analizaremos mediante distintos casos de prueba y, finalmente, veremos la performance de cada uno de los métodos ante distintas situaciones para poder decidir cuál es la búsqueda que nos conviene utilizar en cada caso.

Estructuras de datos estáticas – Búsquedas en Arreglos por Maximiliano López se distribuye bajo una Licencia Creative Commons Atribución 4.0 Internacional.

Maximiliano López [email protected] @maxihlopez

Estructuras de Datos Estáticas: Búsquedas

Contenido Contenido ......................................................................................................................... 1 Resumen ........................................................................................................................... 2 Introducción ..................................................................................................................... 2 Estructuras de Datos......................................................................................................... 2 Métodos de Búsqueda...................................................................................................... 3 Búsqueda Secuencial ........................................................................................................ 3 Algoritmo 1 ................................................................................................................................ 4 Algoritmo 2 ................................................................................................................................ 4

Búsqueda Secuencial en Arreglos Ordenados .................................................................. 5 Algoritmo 1 ................................................................................................................................ 6 Algoritmo 2 ................................................................................................................................ 6

Búsqueda Binaria .............................................................................................................. 7 Comparación de los Métodos de Búsqueda..................................................................... 9 Performance de Búsqueda Secuencial ........................................................................... 11 Performance de Búsqueda Secuencial Ordenada .......................................................... 12 Performance de Búsqueda Binaria ................................................................................. 13 Conclusiones ................................................................................................................... 14

1 de 14

Estructuras de Datos Estáticas: Búsquedas

Resumen En este documento explicaremos tres métodos de búsqueda de datos en arreglos, los cuales se caracterizan fundamentalmente por las siguientes propiedades.  Son simples de comprender y de programar.  Son métodos de búsqueda interno, es decir que trabajan buscando el elemento en el mismo arreglo, sin utilizar arreglos auxiliares. Los métodos que analizaremos serán:  Búsqueda Secuencial.  Búsqueda Secuencial Ordenada.  Búsqueda Binaria o Dicotómica. Además de estudiar el funcionamiento de cada uno de los métodos, presentaremos los algoritmos en pseudocódigo y en lenguaje C, los analizaremos mediante distintos casos de prueba y, finalmente, veremos la performance de cada uno de los métodos ante distintas situaciones para poder decidir cuál es la búsqueda que nos conviene utilizar en cada caso. Palabras clave: arreglo, vector, array, estructura de datos estática, búsqueda, búsqueda secuencial, búsqueda binaria.

Introducción Buscar un elemento en un Arreglo es una de las operaciones más frecuentes que realizaremos al trabajar con esta estructura de datos. Es por eso que resulta de suma importancia evaluar distintos métodos de búsqueda para determinar cuál es el apropiado para cada situación. Analizaremos las búsquedas de acuerdo al orden que tienen los elementos en el arreglo, identificando, de este modo, a los 

arreglos ordenados: aquellos que tienen todos los elementos con un mismo orden, ya sea ascendente o descendente.



arreglos desordenados: aquellos en los que no se puede determinar un orden, o bien los elementos están desordenados.

Estructuras de Datos Para los ejemplos utilizaremos las siguientes estructuras de datos CONSTANTES MAX = 10 TIPOS T_ARR_ENT = arreglo de MAX de ENTEROS 2 de 14

Estructuras de Datos Estáticas: Búsquedas

Métodos de Búsqueda Búsqueda Secuencial La Búsqueda Secuencial es la forma más intuitiva que tenemos de buscar un elemento dentro de un conjunto de datos. Consiste en evaluar cada uno de los elementos, comenzando desde el primero, hasta encontrar el dato o bien hasta haber recorrido todo el vector. De este modo cada elemento visitado se evalúa para determinar si es el Dato a buscar. Este proceso termina cuando se encuentra el Dato o bien cuando se visitaron a todos los elementos del arreglo y el dato no estaba.

El proceso lo podemos especificar en los siguientes pasos: 1. Si hay un primer elemento, se posiciona en él. 2. Se verifica si el elemento actual es el que se está buscando. Si lo es, entonces ya se puede determinar que el Dato está en el arreglo y se encuentra en la posición actual. 3. Si no se encontró en el paso anterior se avanza en el arreglo a la posición siguiente. 4. Si hay otro elemento en el arreglo sin verificar y no se encontró el dato, vuelve al paso 2, sino significa que el elemento no se encuentra en el arreglo. La Búsqueda Secuencial finalizará, entonces, cuando:  Se encuentra el dato.  Se llega al final del arreglo.

3 de 14

Estructuras de Datos Estáticas: Búsquedas

Veamos dos algoritmos equivalentes para implementar este método.

Algoritmo 1 PRE{CE>=0, CE