búsqueda binaria

En ciencias de la computación y matemáticas, la búsqueda binaria, también conocida como búsqueda de intervalo medio​ o búsqueda logarítmica,​ es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado.​​ Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre. La búsqueda binaria es computada en el peor de los casos en un tiempo logarítmico, realizando comparaciones, donde n es el número de elementos del arreglo y log es el logaritmo. La búsqueda binaria requiere solamente O(1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos en el array.​ Aunque estructuras de datos especializadas en la búsqueda rápidas como las tablas hash pueden ser más eficientes, la búsqueda binaria se aplica a un amplio rango de problemas de búsqueda. Aunque la idea es simple, implementar la búsqueda binaria correctamente requiere atención a algunos detalles como su condición de parada y el cálculo del punto medio de un intervalo. Existen numerosas variaciones de la búsqueda binaria. Una variación particular (cascada fraccional) acelera la búsqueda binaria para un mismo valor en múltiples arreglos.