Etiqueta: algoritmos

Búsqueda binaria o dicotómica

en por Donnie Rocken Informática, Javascript/jquery, Lenguajes de programación, Matemáticas-CienciasDeja un comentario

Durante el corto tiempo que tuve cuenta en CuriousCat (lo borré porque para recibir insultos anónimos ya me llega con Tweeter y los comentarios de este blog) alguien me pidió que escribiera sobre la diferencia entre una búsqueda binaria y una búsqueda dicotómica. Eso se lo contesté rápidamente allí: búsqueda dicotómica y búsqueda binaria son sinónimos, no hay diferencia.

¿En qué consiste la búsqueda binaria?

Cuando hablamos de búsqueda binaria hablamos de un algoritmo, una serie de instrucciones para que un programa informático realice una tarea. Concretamente de un algoritmo de búsqueda, es decir, la serie de instrucciones necesarias para encontrar un valor dentro de una colección de valores. La búsqueda binaria está pensada para buscar un elemento dentro de una colección ordenada. Vamos a explicar cómo funciona con un ejemplo: imagínate que tuvieras una lista con todos los habitantes de Barcelona ordenada por la primera letra de su apellido, tienes que buscar a alguien que se apellida «Martínez» ¿te pondrías a mirar la lista desde el principio hasta llegar a ese nombre? Son millones de comprobaciones. Ese procedimiento sería el de una búsqueda lineal: comprobar todos los valores hasta encontrar el deseado, funciona pero es muy lento, tiene utilidad cuando no queda más remedio (una colección desordenada) pero es demasiado ineficiente para una lista ordenada.

Aplicando una búsqueda binaria a ese ejemplo lo que haríamos sería encontrar primero el valor del medio de la lista, dividir la lista en dos mitades y comprobar si el valor intermedio es el que buscamos, es menor o es mayor. Si se diera la casualidad de que es el que buscamos la búsqueda ya estaría finalizada, si el valor intermedio es menor descartaríamos la mitad inferior de la lista y si es mayor descartaríamos la mitad superior. Ahora que localizamos en qué mitad tiene que estar nuestro valor repetimos el procedimiento sobre esa mitad, creando otras dos mitades y de nuevo repitiendo el procedimiento hasta dar con nuestro valor. En cada iteración descartamos la mitad de los datos que teníamos, lo que reduce el tiempo de búsqueda respecto a la lineal.

¿Se usa este algoritmo?

La mayoría de lenguajes de programación o frameworks ya tienen funciones de búsquea integradas muy bien optimizadas, así que no es habitual que alguien tenga que escribir una función de búsquea binaria, excepto en ejercicios académicos para aprender algoritmia. Yo personalmente he utilizado este método para buscar entre conjuntos de datos manualmente, cuando no disponía de un índice. Aquí abajo os dejo una implementación del algoritmo en Javascript:

function buscaDicotomica(valor, conjunto) {
    //valor es lo que vamos a buscar, cojunto es el array donde lo buscamos
    var ini = 0;    //inicio del array
    var fin = conjunto.length - 1;   //fin del array
    var pos = -1;
    var finaliza = false;
    var media;
 
    while (finaliza === false && ini<= fin) {
        media= Math.floor((ini+ fin)/2);
        if (conjunto[media] == valor) {
            finaliza = true;
            pos  = media;
        } else if (conjunto[media] > valor) {  //si está en la mitad inferior
            fin= media - 1;
        } else {  //si está en la mitad superior
            ini= media+ 1;
        }
    }
    return pos;
}

Ordenación de burbuja en Javascript

en por Donnie Rocken Informática, Javascript/jquery, Lenguajes de programación1 comentario

El método del intercambio directo, también llamado ordenación de burbuja (bubble sort en inglés), es un algoritmo de ordenamiento extremadamente sencillo que suele ser un ejercicio clásico en los cursos de programación para entender el uso de los bucles anidados en otros bucles. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Esto hace necesario revisar varias veces toda la lista, hasta que no se necesiten más intercambios. Por ello se trata de un algoritmo lento y poco eficiente.

La implementación de dicho algoritmo en una función de Javascript que recibe un array desordenado sería la siguiente:

//la función recibe un array desordenado
function burbuja(arr) {
 //Primer bucle, recore todo el array
 for (var i = 0; i &lt; arr.length; i++) {
   //segundo bucle, va ordenando los elementos.
   for(var j=0; j  arr[j + 1]) {
       if(arr[j]>arr[j+1]){
         var el1 = arr[j]; 
         arr[j] = arr[j + 1]; 
         arr[j + 1] = el1;
       }      
     }
   }
  }
  //al acabar la ordenación devulve el array,
  //ahora ordenado
  return arr;
}