Algoritmo de búsqueda binaria

Vista previa del material en texto

El algoritmo de búsqueda binaria es un método de búsqueda eficiente que se utiliza para 
encontrar un elemento específico en una lista ordenada. A diferencia de la búsqueda 
secuencial, que recorre todos los elementos en orden lineal, la búsqueda binaria divide 
repetidamente la lista en dos mitades y determina en qué mitad se encuentra el elemento 
buscado. 
 
El algoritmo de búsqueda binaria sigue estos pasos: 
 
Establecer los límites: Inicialmente, se establecen los límites inferior y superior de la lista. El 
límite inferior apunta al primer elemento de la lista, mientras que el límite superior apunta al 
último elemento. 
 
Calcular el punto medio: Se calcula el punto medio de la lista sumando el límite inferior y el 
límite superior, y dividiendo el resultado por 2. Esto nos proporciona el índice del elemento 
central. 
 
Comparar con el elemento buscado: Se compara el elemento en el punto medio con el 
elemento buscado. Si son iguales, se ha encontrado el elemento y se devuelve su posición. 
 
Actualizar los límites: Si el elemento en el punto medio es mayor que el elemento buscado, se 
actualiza el límite superior para excluir la mitad superior de la lista. Si es menor, se actualiza el 
límite inferior para excluir la mitad inferior de la lista. 
 
Repetir el proceso: Se repiten los pasos 2-4 hasta que se encuentre el elemento buscado o los 
límites se crucen. Si los límites se cruzan y el elemento no se ha encontrado, se considera que 
el elemento no está presente en la lista. 
 
El algoritmo de búsqueda binaria tiene una complejidad temporal de O(log n), donde n es el 
número de elementos en la lista. Esto lo hace extremadamente eficiente para grandes 
conjuntos de datos. 
 
Es importante destacar que el algoritmo de búsqueda binaria requiere que la lista esté 
ordenada. Si la lista no está ordenada, se debe realizar una operación de ordenamiento previa 
utilizando algún algoritmo de ordenamiento adecuado, como el ordenamiento rápido o el 
ordenamiento por mezcla. 
 
En resumen, el algoritmo de búsqueda binaria es utilizado para encontrar eficientemente un 
elemento en una lista ordenada. Divide repetidamente la lista en dos mitades y compara el 
elemento buscado con el elemento en el punto medio. Basado en la comparación, actualiza los 
límites y repite el proceso hasta encontrar el elemento o determinar que no está presente. 
Tiene una complejidad temporal de O(log n), lo que lo hace muy eficiente para grandes 
conjuntos de datos. Comprender este algoritmo nos permite realizar búsquedas rápidas y 
eficientes en listas ordenadas.