Búsqueda lineal y búsqueda binaria

Búsqueda Lineal

Método de búsqueda que recorre secuencialmente cada elemento de una lista.

Complejidad temporal de búsqueda lineal

O(n), donde n es el número de elementos en la lista.

Verdadero o falso: Busca en listas ordenadas.

Falso. Funciona en listas desordenadas y ordenadas.

Cómo se realiza la búsqueda lineal?

Se compara el elemento buscado con cada elemento de la lista uno a uno.

Ventajas de búsqueda lineal

- Sencillez - No requiere ordenamiento previo - Útil para listas pequeñas.

Desventajas de búsqueda lineal

- Ineficiente en listas grandes - Altos tiempos de búsqueda.

Cuando usar búsqueda lineal

Cuando la lista es pequeña o no está ordenada.

Ejemplo de búsqueda lineal

Buscar el número 5 en la lista [3, 5, 8, 1]. Resultado: se encuentra en la posición 1.

¿Qué retorna si no se encuentra el elemento?

Retorna -1 o un mensaje de 'no encontrado'.

Búsqueda lineal en arrays

Funciona de manera similar a listas, revisando cada índice secuencialmente.

Pseudocódigo de búsqueda lineal

for i from 0 to n-1: if lista[i] == elemento: return i

Comparar búsqueda lineal y búsqueda binaria.

Búsqueda lineal: O(n); Búsqueda binaria: O(log n).

¿Puede ser recursiva la búsqueda lineal?

Sí, aunque es menos común que la iterativa.

Qué tipo de datos se puede buscar

Cualquier tipo: números, cadenas, objetos.

Estructura de datos para búsqueda lineal

Listas, arrays y vectores.

Caso peor en búsqueda lineal

Cuando el elemento buscado está al final o no está presente.

Búsqueda lineal es adecuada para:

Listas cortas y cuando no hay tiempo para ordenar.

True o falso: Requiere estructura de datos específica.

Falso. No necesita una estructura específica.

Ejemplo de implementación en Python

def busqueda_lineal(lista, elemento): for i in range(len(lista)): if lista[i] == elemento: return i return -1

Uso en aplicaciones reales

Buscar elementos en listas de usuarios, inventarios, etc.

¿Qué es la búsqueda binaria?

Método de búsqueda eficiente en listas ordenadas. Divide y conquista.

Condición para aplicar búsqueda binaria.

La lista debe estar ordenada, ya sea de forma ascendente o descendente.

¿Cuántas comparaciones realiza la búsqueda binaria?

Realiza como máximo $\displaystyle ext{log}_2(n) + 1$ comparaciones, donde $\displaystyle n$ es el tamaño de la lista.

Paso inicial de búsqueda binaria.

Definir índices: $\displaystyle inicio = 0$ y $\displaystyle fin = n - 1$.

¿Qué se hace en cada iteración?

Calcular el índice medio: $\displaystyle mid = \frac{inicio + fin}{2}$.

¿Qué ocurre si el elemento medio es el buscado?

Se ha encontrado el elemento, se retorna el índice $\displaystyle mid$.

¿Cómo se ajustan los índices si el elemento es menor?

Actualizar: $\displaystyle fin = mid - 1$.

¿Cómo se ajustan los índices si el elemento es mayor?

Actualizar: $\displaystyle inicio = mid + 1$.

Cuando se termina la búsqueda binaria.

Cuando $\displaystyle inicio > fin$, el elemento no está en la lista.

¿Qué tipo de listas se pueden usar?

Listas estáticas o dinámicas siempre que estén ordenadas.

¿Cuál es la complejidad temporal?

Complejidad: $\displaystyle O( ext{log} ext{n})$ en el mejor y peor caso.

¿Qué es el caso base en búsqueda binaria?

Cuando $\displaystyle inicio$ es igual a $\displaystyle fin$, se encuentra un único elemento.

Ejemplo: buscar 5 en [1, 3, 5, 7, 9]

Iteraciones: 1. $\displaystyle mid=2$ (5 encontrado) → índice 2.

¿True o False? La búsqueda binaria se puede usar en listas no ordenadas.

False. Solo en listas ordenadas.

Ventajas de búsqueda binaria.

- Eficiencia - Menos comparaciones - Buen rendimiento en datos grandes

¿Qué es un árbol binario de búsqueda?

Estructura donde cada nodo tiene como máximo dos hijos, ordenados.

Desventajas de la búsqueda binaria.

- Requiere lista ordenada - No es dinámica

¿Qué tipo de algoritmo es la búsqueda binaria?

Algoritmo de divide y vencerás.

Aplicaciones de la búsqueda binaria.

Buscadores, bases de datos, algoritmos de ordenación.

Complejidad espacial de búsqueda binaria.

Complejidad: $\displaystyle O(1)$ si se usa iterativa.

¿Qué es la búsqueda lineal?

Método que examina cada elemento secuencialmente hasta encontrar el objetivo.

Búsqueda binaria vs. búsqueda lineal

La búsqueda binaria es más rápida para listas ordenadas, mientras que la lineal no requiere orden.

Complejidad de búsqueda lineal

O(n), donde n es el número de elementos.

¿Qué se necesita para búsqueda binaria?

Una lista ordenada para aplicar el algoritmo de manera eficiente.

Ventaja de búsqueda binaria

Reduce el número de comparaciones al dividir la lista en mitades.

¿La búsqueda lineal es eficiente en listas grandes?

Falso, es ineficiente en grandes volúmenes de datos debido a su complejidad O(n).

¿Cómo se implementa la búsqueda binaria?

1. Definir límites bajo y alto. 2. Calcular el medio. 3. Comparar y ajustar límites.

Número de comparaciones en búsqueda binaria

Log₂(n) comparaciones en el peor de los casos.

Condición para usar búsqueda lineal

No requiere que la lista esté ordenada, útil en listas desordenadas.

¿La búsqueda binaria es aplicable a cualquier lista?

Falso; requiere que la lista esté ordenada para funcionar correctamente.

¿Cuál es más rápida: búsqueda lineal o binaria?

Búsqueda binaria es más rápida en listas ordenadas, especialmente grandes.

Complejidad espacial de búsqueda lineal

O(1), utiliza espacio constante.

Eficiencia de búsqueda lineal

Peor en listas grandes; cada elemento se revisa hasta encontrar el objetivo.

Búsqueda binaria: ¿divide o multiplica?

Divide; reduce el número de elementos a comparar a la mitad en cada paso.

Ejemplo de búsqueda lineal

Buscar el número 5 en [1, 3, 5, 7]: se comprueba cada elemento hasta encontrarlo.

Búsqueda binaria: límite inferior

Límite inferior se ajusta a medio + 1 si el objetivo es mayor que el medio.

¿Cuándo es mejor no usar búsqueda binaria?

Cuando la lista está desordenada o con pocos elementos.

Comparar tiempo de ejecución

Búsqueda lineal puede tardar n; búsqueda binaria tarda log₂(n).

¿Búsqueda lineal es siempre más lenta?

No necesariamente; puede ser más rápida en listas pequeñas o desordenadas.

Condiciones previas para búsqueda binaria

Lista ordenada; de lo contrario, el resultado será incorrecto.

Aplicación de búsqueda lineal

Buscar un número en una lista no ordenada.

¿La búsqueda binaria necesita datos ordenados?

Sí, requiere que los datos estén ordenados previamente.

Ejemplo de búsqueda lineal

Buscar el número 5 en la lista [3, 1, 4, 5, 9]. Resultado: índice 3.

¿Verdadero o falso? La búsqueda lineal es más rápida que la binaria.

Falso. La búsqueda binaria es más rápida en listas ordenadas.

Complejidad temporal de búsqueda lineal

O(n), donde n es el número de elementos.

Complejidad temporal de búsqueda binaria

O(log n), donde n es el número de elementos.

Ejemplo de búsqueda binaria

Buscar el número 6 en la lista [1, 2, 3, 6, 8]. Resultado: índice 3.

¿Qué tipo de datos se pueden buscar?

Cualquier tipo, como enteros, cadenas, etc., siempre que sean comparables.

Ventajas de la búsqueda binaria

- Más rápida en listas grandes - Menos comparaciones necesarias

Desventajas de la búsqueda lineal

- Lenta para listas grandes - Ineficiente en comparación con binaria

Caso práctico: búsqueda en un directorio

Usar búsqueda lineal para encontrar un nombre en un directorio desordenado.

¿Los algoritmos de búsqueda son recursivos?

La búsqueda binaria puede ser recursiva o iterativa; la lineal es generalmente iterativa.

Ejemplo de aplicación en programación

Encontrar el índice de un elemento en un array utilizando ambos métodos.

¿Cuándo usar búsqueda lineal?

Cuando la lista es pequeña o no está ordenada.

Criterios para elegir búsqueda binaria

Lista ordenada y tamaño considerable.

Ejemplo de búsqueda binaria en acción

Lista: [10, 20, 30, 40], buscar 20. Resultado: índice 1.

¿Qué es un 'nodo' en búsquedas?

Es un elemento individual en una estructura de datos, como un árbol.

Estadísticas de eficiencia

Búsqueda lineal: O(n), Búsqueda binaria: O(log n).

Diferencia en la implementación

Búsqueda lineal: simple; búsqueda binaria: requiere cálculos de índices.

Criterio de parada en búsqueda lineal

Elemento encontrado o se recorren todos los elementos.