Binary Search

Binary Search o búsqueda binaria, es una búsqueda también llamada búsqueda de intervalo medio o logarítmica (de acuerdo a su Big O Notation).

Roberto Tejeda

Estimated reading time: 2 minute(s)
March 12, 2019

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:

  1. Se inicializan 3 variables: indiceInferior con 0, indiceSuperior con el tamaño del arreglo y elementoMedio la mitad entre ambos índices.
  2. Si el elemento que está en medio es igual al que buscamos, terminamos el algorirmo.
  3. Si es mayor, actualizamos el indiceInferior que toma el valor del elementoMedio
  4. Si es menor, actualizamos el indiceSuperior que toma el valor del elementoMedio
  5. Volemos a comarar hasta que encontremos el valor deseado o la diferencia entre indiceSuperiorindiceInferior sea menor o igual a 1.

El valor sería encontrado en 3 iteraciones de nuestro algoritmo. Esto nos da una notación de tiempo de O log(n), mucho mas eficiente que la búsqueda lineal que sería O(n). Este tipo de algoritmos también son llamados in place, ya que no requieren estructuras de datos adicionales (otro arreglo) para encontrar el resultado.

binary search
var binarySearch = (lookUp) => {
let numbers = [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30];
let limitLeft = 0;
let limitRight = numbers.length;
let index = Math.round(numbers.length / 2);
let count = 0;
//Pudiera darse el caso que encontremos el valor deseado incluso antes
//de iniciar a iterar en nuestro arreglo
if(numbers[index] === lookUp) {
return 'Number ' lookUp ' found at position ' index ' in 0 iterations.';
} else {
while(numbers[index] !== lookUp && (limitRight - limitLeft) > 1) {
//Contador de interaciones
count ;
//El número es mas grande que nuestro elemento medio,
//actualizaremos nuestro límite inferior al punto medio actual
if(lookUp > numbers[index]) {
limitLeft = index;
index = Math.round((limitRight-limitLeft) / 2);
}
//El número es mas pequeño que nuestro elemento medio,
//actualizaremos nuestro límite superior al punto medio actual
else if(lookUp < numbers[index]) {
limitRight = index;
index -= Math.round((limitRight-limitLeft) / 2);
}
//Llevamos a cabo la comparación, si el elemento es encontrado,
//terminamos nuestro ciclo
if (numbers[index] === lookUp) {
return 'Number ' lookUp ' found at position ' index ' in ' count ' iterations.';
}
}
//No se encontró el elemento
return 'Number ' lookUp ' not found';
}
};

console.log(binarySearch(24));
Búsqueda Binaria

Aquí una liga con una buena referencia y amplia explicación de la búsqueda binaria.

Share this post: LinkedIn LinkedIn Logo Facebook Facebook Logo

About Aviada

With Aviada’s expertise in staff augmentation, hiring professionals in Mexico has never been easier.
By providing us with a job description, you can harness the benefits of Employer Of Record Services and trust Aviada to locate the ideal candidate to meet your needs, seamlessly taking care of the entire process.

Aviada calificada #1 en Best Place to Code 2021

Best Place to Code® es un programa para identificar y premiar a compañías que hacen esfuerzos por ofrecer las mejores condiciones de trabajo para profesionales en tecnologías de la información. Esta distinción es operada por Software Guru.
BPTC Logo