# Algoritmos de Búsqueda La capacidad de encontrar información específica dentro de un conjunto de datos es una operación fundamental en la informática. Desde buscar un nombre en una lista de contactos hasta localizar un archivo en un disco duro, los algoritmos de búsqueda son omnipresentes. Dos de los métodos más básicos y ampliamente estudiados para esta tarea son la **búsqueda lineal** y la **búsqueda binaria**. Aunque ambos tienen el mismo objetivo, difieren drásticamente en su enfoque, sus requisitos y, crucialmente, en su eficiencia. ## Búsqueda Lineal (o Secuencial) La búsqueda lineal es el algoritmo de búsqueda más sencillo y directo. Su principio es examinar cada elemento de una lista o arreglo de datos, uno por uno, en secuencia, hasta que se encuentra el elemento deseado o se ha revisado toda la lista sin éxito. ### Principio de Funcionamiento El algoritmo comienza en el primer elemento de la lista y lo compara con el valor que se busca. Si coinciden, la búsqueda termina y se devuelve la posición del elemento. Si no coinciden, se pasa al siguiente elemento y se repite el proceso. Este procedimiento continúa hasta que se encuentra el elemento o se llega al final de la lista. Si se alcanza el final de la lista y el elemento no ha sido encontrado, se concluye que el elemento no está presente. > **Definición:** La **búsqueda lineal** (o secuencial) es un algoritmo que verifica cada elemento de una lista de datos en orden, uno a uno, hasta encontrar el valor deseado o hasta que se haya revisado toda la lista. ### Condición de Ordenación Una de las ventajas clave de la búsqueda lineal es que **no requiere que la lista de datos esté ordenada**. Funciona igualmente bien en arreglos desordenados como en ordenados, lo que la hace versátil para cualquier tipo de colección de datos. ### Algoritmo (Pseudocódigo) ``` funcion busquedaLineal(arreglo, valorBuscado): para i desde 0 hasta longitud(arreglo) - 1: si arreglo[i] es igual a valorBuscado: retornar i // Se encontró el valor en la posición i retornar -1 // El valor no se encontró en el arreglo ``` ### Ejemplo Paso a Paso Consideremos un arreglo $A = [15, 7, 23, 4, 10]$ y queremos buscar el $valorBuscado = 23$. 1. **Paso 1:** $i = 0$. $arreglo[0]$ es $15$. $15 \neq 23$. Continuar. 2. **Paso 2:** $i = 1$. $arreglo[1]$ es $7$. $7 \neq 23$. Continuar. 3. **Paso 3:** $i = 2$. $arreglo[2]$ es $23$. $23 = 23$. ¡Encontrado! Retornar la posición $2$. Si el $valorBuscado$ fuera $5$, el algoritmo recorrería todo el arreglo y, al no encontrarlo, retornaría $-1$. ### Número de Pasos y Complejidad ($O(n)$) La eficiencia de un algoritmo se mide por el número de operaciones que realiza en función del tamaño de la entrada. Para la búsqueda lineal, en el peor de los casos (cuando el elemento buscado está al final de la lista o no está presente), el algoritmo debe examinar cada uno de los $N$ elementos del arreglo. Por lo tanto, el número de pasos es directamente proporcional al tamaño del arreglo. Esto se expresa en la notación de la complejidad asintótica como **$O(n)$**, donde $n$ es el número de elementos en la lista. Esto significa que si el tamaño de la lista se duplica, el tiempo de ejecución (y el número de operaciones) también se duplica aproximadamente. Did you know que la búsqueda lineal es el algoritmo de búsqueda más fácil de implementar y comprender, y a menudo es suficiente para conjuntos de datos pequeños? ## Búsqueda Binaria La búsqueda binaria es un algoritmo de búsqueda mucho más eficiente que la búsqueda lineal, pero con una restricción importante: **requiere que la lista de datos esté previamente ordenada**. ### Principio de Funcionamiento La búsqueda binaria opera bajo el principio de "divide y vencerás". En lugar de examinar cada elemento secuencialmente, la búsqueda binaria divide repetidamente la porción de la lista en la que podría estar el elemento buscado a la mitad. Compara el valor buscado con el elemento central de la