Algoritmos de búsqueda binaria

Vista previa del material en texto

Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
Algoritmos de búsqueda binaria 
 
Los algoritmos de búsqueda binaria son un tipo de 
algoritmo de búsqueda que se utiliza para encontrar un 
elemento específico dentro de una estructura de datos 
ordenada. Estos algoritmos funcionan dividiendo 
repetidamente la estructura de datos en dos mitades, 
hasta que se encuentra el elemento buscado. 
 
Ideas principales para estudiantes de universidad 
 
Para los estudiantes de universidad, es importante 
comprender las siguientes ideas principales sobre los 
algoritmos de búsqueda binaria: 
 
Los algoritmos de búsqueda binaria son eficientes para 
estructuras de datos ordenadas. 
Los algoritmos de búsqueda binaria son más eficientes 
que los algoritmos de búsqueda lineal para estructuras 
de datos grandes. 
Los algoritmos de búsqueda binaria requieren que la 
estructura de datos esté ordenada. 
Recomendaciones para estudiantes de universidad 
 
Para los estudiantes de universidad que están 
aprendiendo sobre los algoritmos de búsqueda binaria, 
se recomiendan las siguientes actividades: 
 
Practicar mucho. La mejor manera de aprender sobre 
los algoritmos de búsqueda binaria es practicar con 
frecuencia. 
Buscar ayuda cuando sea necesario. Si tienes 
problemas para entender un concepto o resolver un 
problema, no dudes en 
pedir ayuda a un 
profesor o a un tutor. 
Participar en proyectos. 
Trabajar en proyectos te 
ayudará a aplicar tus 
conocimientos sobre los 
algoritmos de búsqueda 
binaria en el mundo 
real. 
Explicación 
 
Los algoritmos de 
búsqueda binaria se 
pueden implementar de 
diferentes maneras, 
pero el enfoque más 
común es el siguiente: 
 
Comenzar en la mitad 
de la estructura de 
datos. 
Comparar el elemento 
buscado con el 
elemento que se 
encuentra en la mitad 
de la estructura de 
datos. 
Si el elemento buscado 
es igual al elemento que 
se encuentra en la mitad 
de la estructura de 
datos, devolver la 
posición del elemento 
buscado. 
Si el elemento buscado 
es menor que el 
elemento que se 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
encuentra en la mitad de la estructura de datos, buscar 
en la mitad inferior de la estructura de datos. 
Si el elemento buscado es mayor que el elemento que 
se encuentra en la mitad de la estructura de datos, 
buscar en la mitad superior de la estructura de datos. 
Repetir los pasos 2-5 hasta que se encuentre el 
elemento buscado o hasta que se llegue al final de la 
estructura de datos. 
Ejemplo 
 
Imaginemos que tenemos una lista de números del 1 al 
10, y queremos encontrar el número 5. El siguiente 
algoritmo de búsqueda binaria nos ayudará a encontrar 
el número buscado: 
 
Python 
def buscar_binario(lista, numero): 
 inicio = 0 
 fin = len(lista) - 1 
 while inicio <= fin: 
 medio = (inicio + fin) // 2 
 if lista[medio] == numero: 
 return medio 
 elif lista[medio] < numero: 
 inicio = medio + 1 
 else: 
 fin = medio - 1 
 return -1 
Usa el código con precaución. Más información 
Este algoritmo funciona dividiendo la lista en dos 
mitades iguales. Luego, compara el elemento buscado 
con el elemento que se encuentra en la mitad de la 
lista. Si el elemento 
buscado es igual al 
elemento que se 
encuentra en la mitad 
de la lista, el algoritmo 
devuelve la posición de 
ese elemento. Si el 
elemento buscado es 
menor que el elemento 
que se encuentra en la 
mitad de la lista, el 
algoritmo busca en la 
mitad inferior de la lista. 
Si el elemento buscado 
es mayor que el 
elemento que se 
encuentra en la mitad 
de la lista, el algoritmo 
busca en la mitad 
superior de la lista. El 
algoritmo repite estos 
pasos hasta que 
encuentra el elemento 
buscado o hasta que 
llega al final de la lista. 
 
Complejidad 
 
La complejidad de los 
algoritmos de búsqueda 
binaria es O(log n), 
donde n es el tamaño 
de la estructura de 
datos. Esto significa que 
el tiempo de ejecución 
del algoritmo es 
proporcional al logaritmo 
del tamaño de la 
estructura de datos. 
 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
Eficiencia 
 
Los algoritmos de búsqueda binaria son eficientes para 
estructuras de datos ordenadas. Son mucho más 
eficientes que los algoritmos de búsqueda lineal para 
estructuras de datos grandes. Sin embargo, los 
algoritmos de búsqueda binaria requieren que la 
estructura de datos esté ordenada. 
 
Conclusión 
 
Los algoritmos de búsqueda binaria son una 
herramienta fundamental en la programación. Los 
estudiantes de universidad deben comprenderlos a 
fondo para poder resolver problemas informáticos 
complejos.