Búsqueda binaria en un arreglo ordenado
Acabo de empezar a aprender algunos algoritmos básicos, pero algo me ha estado confundiendo acerca del algoritmo de búsqueda binaria.
Según entiendo, la complejidad temporal máxima de una búsqueda binaria es O(log(n)), donde el logaritmo es en base 2.
Sin embargo, cuando se utiliza la fórmula en valores de N que no son potencias de 2, se obtiene un valor no entero.
Lo que me confunde es si, por ejemplo, obtienes 3.3, ¿eso significa que son un máximo de 3 pasos o 4 pasos?
Obtienes el valor 3.3 cuando usas un arreglo donde n = 10. Dicho esto, conté manualmente el número de pasos y obtuve 4, así que asumo que se redondea hacia arriba.
Pero en mi libro de texto, dice que en un arreglo donde n=10000, se necesitan 13 pasos como máximo. Al aplicar esa fórmula logarítmica obtengo 13.2, lo que significa que en este caso se redondeó hacia abajo.
He intentado hacer una búsqueda binaria con arreglos de diferentes tamaños y he encontrado casos en los que debo redondear hacia abajo para obtener la respuesta del libro y casos en los que debo redondear hacia arriba.
No estoy seguro de cuándo se debe redondear hacia arriba o hacia abajo, o si estoy cometiendo otro error por completo.
Si alguien me puede dar un ejemplo, ¿podría por favor usar un arreglo de tamaño 100000? Ya que en el libro dice un máximo de 16 veces, pero cuando divido manualmente 100000 entre 2 hasta llegar a 1, obtengo 17 veces.
¡Gracias de antemano!
davy.ai
Cuando se trata de valores que no son potencias de 2, el resultado de la función logarítmica no siempre será un número entero. En este caso, como mencionaste, puede ser confuso si redondear hacia arriba o hacia abajo al calcular el número máximo de pasos en una búsqueda binaria.
En general, se recomienda redondear hacia arriba al número entero más cercano al calcular el número máximo de pasos. Esto se debe a que redondear hacia abajo podría resultar en una subestimación del número real de pasos requeridos.
Por ejemplo, al usar un arreglo de tamaño 100000, el número máximo de pasos en una búsqueda binaria se puede calcular de la siguiente manera:
log(100000) / log(2) = 16.609
Redondeando hacia arriba al número entero más cercano, obtenemos un máximo de 17 pasos.
Sin embargo, es importante tener en cuenta que el número máximo de pasos en una búsqueda binaria es un concepto teórico y no siempre se logrará en la práctica. Factores como la distribución de datos y los detalles de implementación pueden afectar el número real de pasos requeridos.
En resumen, al utilizar un valor que no sea potencia de 2 para el tamaño de un arreglo en una búsqueda binaria, se recomienda redondear hacia arriba al número entero más cercano al calcular el número máximo de pasos.