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

Algoritmos

  • Inicio
  • Blog
  • Algoritmos
  • Binary Search

Binary Search

  • publicado por Roberto Tejeda
  • Categorías Algoritmos, Blog
  • Fecha 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.

Etiqueta: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.

Publicación anterior

Big O Notation
marzo 12, 2019

Siguiente publicación

Linear Search
marzo 24, 2019

También te puede interesar

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

Cursos En Línea

Experiencia

Acceso Gratuito

Aviada Academy es una Asociación Civil sin fines de lucro que tiene por objetivo el acercar contenidos educativos gratuitos a estudiantes, recién egresados o personas en búsqueda de mejores oportunidades laborales, con el fin de incrementar su calidad personal y profesional.
  • Blvd. Luis Donaldo Colosio 671, Col. Santa Fe, Hermosillo, Sonora, México.
+52 662 689 2905 ext 40059
academy@aviada.mx
ENLACES DE INTERÉS
  • Vinculación
  • Aviada
  • Aviada en LinkedIn
Academy by Aviada ® 2021. All rights reserved.

Inicie sesión con su cuenta de sitio

¿Perdiste tu contraseña?

¿No eres miembro todavía? Regístrate ahora

Registra una nueva cuenta

¿Es usted miembro? Inicia sesión ahora