Algoritmos de búsqueda
• Los procesos de búsqueda involucran recorrer un arreglo completo con el fin de encontrar algo. Lo más común es buscar el menor o mayor elemento (cuando es puede establecer un orden), o buscar el índice de un elemento determinado.
• Para buscar el menor o mayor elemento de un arreglo, podemos usar la estrategia, de suponer que el primero o el último es el menor (mayor), para luego ir comparando con cada uno de los elementos, e ir actualizando el menor (mayor). A esto se le llama Búsqueda Lineal.
CARACTERÍSTICAS Y PROPIEDADES DE LOS ALGORITMOS
Las
características fundamentales que debe cumplir todo algoritmo son:
- Debe ser preciso y concreto, indicar el orden de cada paso sin ambigüedad.
- Debe estar definido. Si sigues un algoritmo dos o más veces, debes obtener el mismo resultado siempre.
- Debe ser finito, siempre un algoritmo debe terminar en alguno de sus pasos.
- Un algoritmo debe ser legibles, siempre descrito, claro y fácil de leer.
- Debe tener definida tres partes: Entrada, Proceso y Salida.
Algoritmos de Búsqueda
• Definición:
– Para encontrar un dato dentro de un arreglo, para ello
existen diversos algoritmos que varían en
complejidad, eficiencia, tamaño del dominio de búsqueda.
Algoritmos de Búsqueda:
– Búsqueda Secuencial
– Búsqueda Binaria
Búsqueda Secuencial
• Consiste en ir comparando el elemento que se busca con cada elemento del arreglo hasta cuando se encuentra. • Busquemos el elementos ‘u’
Búsqueda Secuencial
• Búsqueda del menor
menor = a[0];
for
(i=1;i<n;i++)
if (
a[i]<menor )
menor=a[i];
• Búsqueda del mayor
mayor=
a[n-1];
for
(i=0;i<n-1;i++)
if (
a[i]>mayor )
mayor=a[i];
• Búsqueda de elemento
encontrado=-1;
for (i=0;i<n;i++)
if ( a[i]==elemento_buscado )
encontrado=i;
Eficiencia y Complejidad
• Considerando la Cantidad de Comparaciones
– Mejor Caso:
• El elemento buscado está en la primera posición. Es decir, se hace una sola comparación
– Peor Caso:
• El elemento buscado está en la última posición. Necesitando igual cantidad de comparaciones que de elementos el arreglo
– En Promedio:
• El elemento buscado estará cerca de la mitad. Necesitando en
promedio, la mitad de comparaciones que de elementos
• Por lo tanto, la velocidad de ejecución depende
linealmente del tamaño del arreglo
Búsqueda Binaria
En el caso anterior de búsqueda se asume que los elementos están en cualquier orden. En el peor de los casos deben hacerse n operaciones de comparación.
Una búsqueda más eficiente puede hacerse sobre un arreglo ordenado. Una de éstas es la Búsqueda Binaria.
La Búsqueda Binaria, compara si el valor buscado está en la mitad superior o inferior. En la que esté, subdivido nuevamente, y así sucesivamente hasta encontrar el valor.
Complejidad y Eficiencia
• Contando Comparaciones
– Mejor Caso:
• El elemento buscado está en el centro. Por lo tanto, se hace una sola comparación
– Peor Caso:
• El elemento buscado está en una esquina. Necesitando log2(n) cantidad de comparaciones
– En Promedio:
• Serán algo como log2(n/2)
• Por lo tanto, la velocidad de ejecución depende logarítmicamente del tamaño del arreglo
Referencias
- https://dmezzadri.com/que-es-un-algoritmo/
- https://www.inf.utfsm.cl/~noell/IWI-131-p1/Tema8b.pdf
- https://es.slideshare.net/JuanNavarro28/algoritmos-de-busqueda-49858452?next_slideshow=1
Comentarios
Publicar un comentario