• Cursos
  • Academia
  • Blog
  • Aviada
Academy
  • Cursos
  • Academia
  • Blog
  • Aviada
    • RegistroIniciar Sesión

Algoritmos

  • Home
  • Blog
  • Algoritmos
  • Binary Search

Binary Search

  • Posted by Roberto Tejeda
  • Categories Algoritmos, Blog
  • Date marzo 12, 2019
Binary Search

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:

  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 indiceSuperior–indiceInferior 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
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.

Tag:algoritmos, Binary Search, Búsqueda Binaria

author avatar
Roberto Tejeda

Egresado Ingeniería en Sistemas Computacionales por el Instituto Tecnológico de Hermosillo en 2004. Actualmente desarrollador de software y Director de Operaciones en Aviada.

Previous post

Big O Notation
marzo 12, 2019

Next post

Linear Search
marzo 24, 2019

You may also like

las 10 habilidades
Las 10 habilidades más deseables por las empresas de acuerdo con el Foro Económico Mundial para el 2025
20 abril, 2021
La nueva normalidad
La nueva normalidad
30 marzo, 2021
crear un tema en Wordpress
Crear un tema hijo en WordPress
5 enero, 2021

Search

Categorías

  • Algoritmos
  • Blog
  • Optimización
  • telecomunicaciones
  • Tutoriales
  • Uncategorized
  • Wordpress

Back to top

Login with your site account

Lost your password?

Not a member yet? Register now

Register a new account

Are you a member? Login now