¿Cómo difieren la búsqueda lineal y binaria?

En términos muy simples, la búsqueda binaria terminó mucho más rápido. ¿Por qué? Imagine que está buscando un valor linealmente en una matriz (verificando un valor después del otro de principio a fin). En cada paso, solo elimina un solo elemento de su búsqueda si no es igual a su valor de búsqueda.

Nota: la búsqueda binaria solo funciona en matrices ordenadas.

En la búsqueda binaria, en cada paso eliminas aproximadamente la mitad de todos los elementos, por lo que después de cada iteración solo estás tratando con la mitad del número de elementos en el anterior. ¿Cómo? Compara su valor de búsqueda con el que está en el medio de la matriz. Si es más grande, significa que no hay forma de que pueda mentir a la mitad izquierda (suponiendo una clasificación de orden creciente de izquierda a derecha). Has eliminado la mitad de los elementos allí mismo. Así que ahora te concentras solo en la mitad derecha y repites el proceso.

La búsqueda lineal solo examina todos los elementos uno por uno y funciona en tiempo lineal [matemática] O (n) [/ matemática]. La búsqueda binaria utiliza el hecho de que los elementos están ordenados y que el elemento que necesita puede compararse con ellos. Al igual que cuando busca un nombre en una guía telefónica, puede comparar la primera letra de los nombres en el medio de la guía telefónica con la primera letra del nombre que está buscando y luego decidir qué mitad buscar. Búsqueda binaria funciona en tiempo logarítmico [matemáticas] O (\ log n). [/ matemáticas]

Es muy simple una vez que entiendes lo que es una búsqueda binaria.

La búsqueda lineal es simplemente buscar a través de una estructura de datos o un conjunto de datos en orden secuencial. Si quisiera buscar la palabra “música” en un diccionario usando la búsqueda lineal, comenzaría en la primera página del diccionario y seguiría pasando páginas secuencialmente hasta llegar a la palabra “música”. Como está buscando en todo el espacio, no es necesario ordenar los datos.

La búsqueda binaria divide el espacio de búsqueda por la mitad, decide qué mitad contendría lo que está buscando y luego repite este proceso con el nuevo espacio de búsqueda. A diferencia de la búsqueda lineal, la búsqueda binaria requiere que se ordenen los datos. Si quisiera buscar la palabra “música” en un diccionario usando la búsqueda binaria, no comenzaría desde el principio y seguiría pasando las páginas. Abriría aproximadamente la mitad del diccionario, vería qué palabra hay en esa página y averiguaría si “música” aparece antes o después de esa palabra. Si “música” aparece antes de esa palabra, limitaré mi búsqueda estrictamente a la primera mitad del libro. Luego miraría la mitad de la primera mitad del libro y repetiría este proceso.

Claramente, puede ver que (suponiendo que los datos estén ordenados) la búsqueda binaria general es más rápida que la búsqueda lineal (no sería más rápido si estuviera buscando “oso hormiguero”). En términos de análisis de tiempo de ejecución, la búsqueda binaria es el ejemplo más fácil de O (logn) y la búsqueda lineal es el ejemplo más fácil de O (n).

La búsqueda lineal es útil cuando la matriz de elementos no está ordenada, mientras que la búsqueda binaria es útil cuando la matriz de elementos está ordenada.