El problema de la búsqueda secuencial y binaria en programación

>

<

El problema de la búsqueda secuencial y binaria en programación

EMPEZAR>

1/16

Introducción

La búsqueda es una de las operaciones más importantes en programación. Consiste en localizar un elemento dentro de una colección de datos, como arreglos, listas o bases de datos. La eficiencia de un algoritmo de búsqueda puede marcar la diferencia en el rendimiento de un programa. Existen diferentes técnicas de búsqueda que se aplican según el tipo de datos y su organización. Dos de las más conocidas son la búsqueda secuencial y la búsqueda binaria, cada una con ventajas y limitaciones.

SIGUIENTE>

2/16

El problema de la búsqueda y su importancia en la programación

El problema surge cuando se desea encontrar un valor específico dentro de un conjunto de datos. La dificultad radica en cómo hacerlo de manera rápida y eficiente, especialmente cuando la cantidad de información es muy grande. Los algoritmos de búsqueda permiten optimizar el acceso a información, reduciendo tiempo de ejecución. Son fundamentales en aplicaciones como sistemas de bases de datos, motores de búsqueda, inteligencia artificial y análisis de datos.

SIGUIENTE>

3/16

La busqueda secuencial y su funcionamiento

La búsqueda secuencial es el método más simple. Consiste en recorrer uno a uno los elementos de la lista hasta encontrar el valor buscado o hasta llegar al final de la estructura. El proceso inicia desde el primer elemento de la lista y se compara con el valor deseado. Si coinciden, se devuelve la posición del elemento. En caso contrario, se continúa hasta que ya no haya más datos por revisar.

SIGUIENTE>

Pasos de búsqueda

SIGUIENTE>

4/16

Ventajas y desventajas de la búsqueda secuencial

Ventajas: Simplicidad de implementación. No requiere datos ordenados. Flexibilidad de datos. No requiere memoria adicional.

Desventajas: Ineficiencia en conjuntos grandes. Complejidad alta. No escalable.

SIGUIENTE>

Ejemplo práctico de búsqueda secuencial

5/16

Supongamos que tenemos la lista [4, 9, 2, 7, 5] y queremos buscar el número 7 dentro de ella. El algoritmo comienza desde el primer elemento y lo compara con el número buscado. Primero compara 4 con 7 y no coincide. Luego avanza al segundo elemento y compara 9 con 7, tampoco coincide. Después revisa el tercer elemento, 2 con 7, y no coincide. Finalmente llega al cuarto elemento, compara 7 con 7 y encuentra el valor buscado. El número 7 se encuentra en la posición 3 si usamos índices desde 0, o en la posición 4 si contamos desde 1. Si intentamos buscar el número 10 en la misma lista, el proceso sería comparar 4 con 10, después 9 con 10, luego 2 con 10, después 7 con 10 y por último 5 con 10. Como ninguno coincide, el algoritmo llega al final de la lista y concluye que el elemento no está presente.

SIGUIENTE>

6/16

¡Vamos a VS Code!

SIGUIENTE>

Complejidad algorítmica

7/16

La búsqueda secuencial es un algoritmo lineal, porque su rendimiento depende directamente del número de elementos en la lista. 1. Caso mejor (Best Case) Ocurre cuando el elemento se encuentra en la primera posición. 2. Caso peor (Worst Case) Ocurre cuando el elemento no existe en la lista o está en la última posición. 3. Caso promedio (Average Case) Asumimos que el elemento buscado puede estar en cualquier posición con igual probabilidad. En promedio, se recorren la mitad de los elementos. Ejemplo: en una lista de 10 elementos, en promedio se harían 5 comparaciones. Formalmente: O(n/2), pero en notación Big-O se simplifica a O(n).

SIGUIENTE>

8/16

Notación Big-O

La notación Big-O es una forma de describir la eficiencia de un algoritmo en términos de tiempo de ejecución o uso de memoria, sin importar el hardware o el lenguaje de programación. Su objetivo es expresar cómo crece el número de operaciones a medida que aumenta el tamaño de la entrada del problema. En Big-O no se consideran los detalles pequeños como constantes o divisiones, ya que lo importante es la tendencia de crecimiento cuando el número de datos se hace muy grande. Por ejemplo, si un algoritmo tarda en promedio n/2 pasos, en Big-O simplemente se escribe O(n), porque lo que importa es que crece de manera lineal con respecto al tamaño de los datos.

SIGUIENTE>

9/16

¿Que es la Busqueda binaria y cómo funciona?

La búsqueda binaria es más eficiente, pero requiere que los datos estén ordenados. Su objetivo es reducir el número de comparaciones dividiendo el conjunto en partes cada vez más pequeñas hasta encontrar el valor buscado. El algoritmo inicia comparando el valor buscado con el elemento central de la lista. Si coincide, se encontró la respuesta. Si el valor es menor, se descarta la mitad superior. Si es mayor, se descarta la mitad inferior. El proceso se repite hasta encontrar el elemento o hasta que no haya más datos.

SIGUIENTE>

10/16

Ventajas y desventajas de la búsqueda binaria

Ventajas:Eficiencia (O(log n)). Ideal para grandes volúmenes de datos. Búsquedas frecuentes. Simplicidad conceptual. Base para otras estructuras.

Desventajas: Requiere datos ordenados. Costo de ordenamiento. Menos eficiente para conjuntos pequeños. Rendimiento en datos dinámicos.

SIGUIENTE>

11/16

Funcionamiento paso a paso

1-. Se necesita que la lista esté ordenada. 2-. Se definen dos índices: low (inicio) y high (final). 3-. Mientras low <= high:Calcular el punto medio: mid = (low + high) / 2. Comparar el valor en mid con el buscado:

• Si es igual → encontrado.
• Si es menor → buscar en la mitad derecha (low = mid + 1).
• Si es mayor → buscar en la mitad izquierda (high = mid - 1).

4-. Si al final low > high → el elemento no está en la lista.

SIGUIENTE>

12/16

Ejemplo rápido

Arreglo: [2, 5, 8, 12, 16, 23, 38, 56], buscar 23. Paso 1: mid=3 → 12 < 23 → buscar derecha. Paso 2: mid=5 → 23 == 23 → encontrado en posición 5. La búsqueda binaria descarta la mitad de los elementos en cada paso, por eso es tan eficiente (O(log n)).

SIGUIENTE>

13/16

¡Vamos a VS Code!

SIGUIENTE>

14/16

Aplicaciones practicas

• Búsqueda en diccionarios o listas grandes.

• Bases de datos.

• Sistemas de archivos.

• Juegos (ej. búsqueda de rangos en puntuaciones).

SIGUIENTE>

¿Cual es la diferencia entre busqueda binaria y secuencial?

15/16

La búsqueda secuencial revisa cada elemento uno por uno hasta encontrar el objetivo, y puede funcionar en listas desordenadas, mientras que la búsqueda binaria divide repetidamente la lista por la mitad para encontrar el elemento, pero requiere que la lista esté previamente ordenada para ser eficiente y correcta.

SIGUIENTE>

16/16

Conclusión

La búsqueda es esencial en programación porque permite acceder a la información de manera eficiente. La búsqueda secuencial destaca por su simplicidad y adaptabilidad, aunque puede ser lenta en grandes volúmenes de datos. En contraste, la búsqueda binaria ofrece mayor rapidez al trabajar con listas ordenadas. Conocer ambas técnicas es fundamental para aplicar la estrategia correcta según las necesidades de cada problema.

SIGUIENTE>

Gracias por su atención 😁

>

<