Qué es una búsqueda binaria o Binary Search
Binary Search o búsqueda binaria, es una búsqueda también llamada de intervalo medio o logarítmica (de acuerdo a su Big O Notation). Parte de una colección de datos ordenada y busca el punto medio, descartando la parte donde no está el elemento y partiendo de nuevo a la mitad el sub conjunto donde si está. Supongamos que tenemos el siguiente arreglo de 15 elementos: [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30]- Primero tenemos que asegurarnos que los datos están ordenados, es un requisito. En este caso si lo están, de menor a mayor.
- Necesitamos saber la posición del número 24 dentro del arreglo.
El algoritmo sería el siguiente:
- Se inicializan 3 variables: indiceInferior con 0, indiceSuperior con el tamaño del arreglo y elementoMedio la mitad entre ambos índices.
- Si el elemento que está en medio es igual al que buscamos, terminamos el algorirmo.
- Si es mayor, actualizamos el indiceInferior que toma el valor del elementoMedio
- Si es menor, actualizamos el indiceSuperior que toma el valor del elementoMedio
- Volemos a comarar hasta que encontremos el valor deseado o la diferencia entre indiceSuperior-indiceInferior sea menor o igual a 1.
Binary Search[/caption]
[pastacode lang="javascript" manual="var%20binarySearch%20%3D%20(lookUp)%20%3D%3E%20%7B%0A%20%20let%20numbers%20%3D%20%5B1%2C%203%2C%204%2C%207%2C%209%2C%2011%2C%2013%2C%2016%2C%2019%2C%2018%2C%2020%2C%2022%2C%2024%2C%2027%2C%2030%5D%3B%0A%20%20let%20limitLeft%20%3D%200%3B%0A%20%20let%20limitRight%20%3D%20numbers.length%3B%0A%20%20let%20index%20%3D%20Math.round(numbers.length%20%2F%202)%3B%0A%20%20let%20count%20%3D%200%3B%0A%20%20%2F%2FPudiera%20darse%20el%20caso%20que%20encontremos%20el%20valor%20deseado%20incluso%20antes%0A%20%20%2F%2Fde%20iniciar%20a%20iterar%20en%20nuestro%20arreglo%0A%20%20if(numbers%5Bindex%5D%20%3D%3D%3D%20lookUp)%20%7B%0A%20%20%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20found%20at%20position%20'%20%2B%20index%20%2B%20'%20in%200%20iterations.'%3B%0A%20%20%7D%20else%20%7B%0A%20%20%20%20while(numbers%5Bindex%5D%20!%3D%3D%20lookUp%20%26%26%20(limitRight%20-%20limitLeft)%20%3E%201)%20%7B%0A%20%20%20%20%20%20%2F%2FContador%20de%20interaciones%0A%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%2F%2FEl%20n%C3%BAmero%20es%20mas%20grande%20que%20nuestro%20elemento%20medio%2C%0A%20%20%20%20%20%20%2F%2Factualizaremos%20nuestro%20l%C3%ADmite%20inferior%20al%20punto%20medio%20actual%0A%20%20%20%20%20%20if(lookUp%20%3E%20numbers%5Bindex%5D)%20%7B%0A%20%20%20%20%20%20%20%20limitLeft%20%3D%20index%3B%0A%20%20%20%20%20%20%20%20index%20%2B%3D%20Math.round((limitRight-limitLeft)%20%2F%202)%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%2F%2FEl%20n%C3%BAmero%20es%20mas%20peque%C3%B1o%20que%20nuestro%20elemento%20medio%2C%0A%20%20%20%20%20%20%2F%2Factualizaremos%20nuestro%20l%C3%ADmite%20superior%20al%20punto%20medio%20actual%0A%20%20%20%20%20%20else%20if(lookUp%20%3C%20numbers%5Bindex%5D)%20%7B%0A%20%20%20%20%20%20%20%20limitRight%20%3D%20index%3B%0A%20%20%20%20%20%20%20%20index%20-%3D%20Math.round((limitRight-limitLeft)%20%2F%202)%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%2F%2FLlevamos%20a%20cabo%20la%20comparaci%C3%B3n%2C%20si%20el%20elemento%20es%20encontrado%2C%0A%20%20%20%20%20%20%2F%2Fterminamos%20nuestro%20ciclo%0A%20%20%20%20%20%20if%20(numbers%5Bindex%5D%20%3D%3D%3D%20lookUp)%20%7B%0A%20%20%20%20%20%20%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20found%20at%20position%20'%20%2B%20index%20%2B%20'%20in%20'%20%2B%20count%20%2B%20'%20iterations.'%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%2F%2FNo%20se%20encontr%C3%B3%20el%20elemento%0A%20%20%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20not%20found'%3B%0A%20%20%7D%0A%7D%3B%0A%0A%20console.log(binarySearch(24))%3B" message="Búsqueda Binaria" highlight="9,17,23,29,34" provider="manual"/]
Aquí una liga con una buena referencia y amplia explicación de la búsqueda binaria.