Estructura De Datos - Algoritmos De Búsqueda
La operación de búsqueda consiste en determinar si un elemento determinado pertenece o no al conjunto de elementos que forman parte integrante de un arreglo o tabla y,en caso afirmativo indica la posición que dicho elemento ocupa.
Los métodos más usados de búsqueda son:
1. Búsqueda secuencial o lineal.
2. Búsqueda binaria o dicotómica.1. Búsqueda secuencial de un vector desordenado: Esta operación consiste en recorrer el vector secuencialmente de izquierda a derecha hasta encontrar el elemento el elemento buscado o hasta alcanzarel final del vector, en cuyo caso finalizará la operación de búsqueda sin haber localizado el elemento en cuestión. En aquellos casos en que el elemento buscado se encuentra repetido, indicará laposición del situado más a la izquierda, es decir, el de menor índice.
Observaciones:
a) elemento corresponde al elementoque ingresa el usuario para ser buscado.
b) N corresponde al tope o largo que posee el vector.
c) vector es el arreglo unidimensional donde se busca el elemento.2. Búsqueda secuencial de un vector ordenado : Esta operación consiste en recorrer el vector secuencialmente de izquierda a derecha hasta encontrar el elemento buscado o hastasobrepasar el valor de dicho elemento, lo qué nos indicará que no se encuentra entre los valores almacenados dentro del vector, no siendo necesario llegar al final para determinar que el valor buscado noexiste. Este método requiere que el vector se encuentre ordenado de menor a mayor.
1. Búsqueda binaria o dicotómica: Estemétodo consiste en acotar el tramo de búsqueda entre dos extremos (extremo izquierdo y extremo derecho), calculando el punto o elemento central de dicho extremo.
Central =(ext_izq+ext_der)/2....
Regístrate para leer el documento completo.