Definición: ¿Qué significa la búsqueda binaria?
Se utiliza un algoritmo de búsqueda binaria para encontrar la posición de un valor específico contenido en una matriz ordenada. Trabajando con el principio de divide y vencerás, este algoritmo de búsqueda puede ser bastante rápido, pero la advertencia es que los datos deben estar ordenados. Funciona iniciando la búsqueda en el medio de la matriz y bajando por la primera mitad inferior o superior de la secuencia. Si el valor de la mediana es más bajo que el valor objetivo, eso significa que la búsqueda debe ir más alto, de lo contrario, debe buscar en la parte descendente de la matriz.
Una búsqueda binaria también se conoce como búsqueda de medio intervalo o búsqueda logarítmica.
Techinfo explica la búsqueda binaria
Una búsqueda binaria es un método rápido y eficiente para encontrar un valor objetivo específico de un conjunto de elementos ordenados. Al comenzar en el medio de la lista ordenada, puede reducir eficazmente el espacio de búsqueda a la mitad determinando si ascender o descender la lista en función del valor mediano en comparación con el valor objetivo.
Por ejemplo, con un valor objetivo de 8 y un espacio de búsqueda de 1 a 11:
- Se encuentra el valor mediano / medio y el puntero se establece allí, que en este caso es 6.
- El objetivo de 8 se compara con 6. Dado que 6 es menor que 8, el objetivo debe estar en la mitad superior.
- El puntero se mueve al siguiente valor (7) y se compara con el objetivo. Es más pequeño, por lo tanto, el puntero se mueve al siguiente valor más alto.
- El puntero ahora está en 8. Comparando esto con el objetivo, es una coincidencia exacta, por lo tanto, se ha encontrado el objetivo.
Usando la búsqueda binaria, el objetivo solo tuvo que compararse con tres valores. En comparación con hacer una búsqueda lineal, habría comenzado desde el primer valor y se habría movido hacia arriba, necesitando comparar el objetivo con ocho valores. Una búsqueda binaria solo es posible con un conjunto ordenado de datos; si los datos están ordenados aleatoriamente, entonces una búsqueda lineal produciría resultados todo el tiempo mientras que una búsqueda binaria probablemente estaría atascada en un bucle infinito.