¿Cómo funciona el algoritmo de búsqueda binaria?
El algoritmo de búsqueda binaria es mucho mas rápido que el algoritmo de búsqueda lineal. A diferencia del algoritmo de búsqueda lineal que elimina un elemento por iteración, el algoritmo de búsqueda binaria elimina la mitad de elementos en cada una de las iteraciones, sin embargo este algoritmo tiene una desventaja, y es que solo funciona con arreglos que se encuentran ordenados.
La búsqueda binaria utiliza Divide and Conquer, el cual consiste dividir el arreglo en 2 partes, tomar un punto medio, verificar si este punto medio es el valor que se busca o de lo contrario mover el inicio o el fin dependiendo de si el punto medio es mayor o menor que el valor buscado.
Ejemplo de búsqueda binaria en javascript
function busquedaBinaria(arr, val) {
let inicio = 0;
let fin = arr.length - 1;
while (inicio <= fin) {
const pm = Math.floor((inicio + fin) / 2);
if (arr[pm] === val) {
return pm;
} else if (arr[pm] < val) {
inicio = pm + 1;
} else {
fin = pm - 1;
}
}
return -1;
}
Time complexity para la búsqueda binaria
En el mejor escenario O(1) En el peor escenario O(log n)
