Capítulo 79: Búsqueda binaria en C

Diario de un programador. Día 181

Búsqueda binaria en C

La búsqueda binaria se debe aplicar en un arreglo ordenado, ya sea de mayor a menor o vice versa. Lo que hace es comparar el valor buscado por el elemento central del arreglo, si son iguales, entonces se da por finalizada la búsqueda, pero si no son iguales, entonces el elemento a buscar se compara con el elemento central y verifica si es mayor o menor que este. Al hacer esto, se  divide el arreglo en dos partes, uno de mayor valor al elemento buscado y otro de menor valor al elemento buscado. Si el elemento buscado es menor al valor central, entonces se seguirá buscando en el arreglo de menor tamaño descartando a la otra parte, no tiene sentido buscar en la otra mitad si todos los números son mayores al número buscado. Es así que se compara nuevamente el valor buscado con el valor central de esta mitad y así sucesivamente hasta encontrar o no encontrar el valor.

Ejemplo:

Supongamos que tengo el siguiente arreglo ordenado:

2,4,5,7,9,11,13,15,17,21,25,30

Lo que necesito verificar es si el número 5 se encuentra en esta lista. Entonces, nuestro algoritmo hará lo siguiente:

Primero, se comparará con el número central de este arreglo.

2,4,5,7,9,11,13,15,17,21,25,30

Entonces, diremos ¿ es 5 (nuestro número) igual a  11 ?

No, no es igual. Entonces ¿ 5 es menor a 11 ?

Si, es menor. Entonces buscaremos en los números que se encuentren antes que el número 11.

Al hacer esta búsqueda dentro de los números menores a 11, es que se crea una especie de división del arreglo. No es una división literalmente como dice la palabra, yo al principio pensé que habría que modificar el tamaño del arreglo a su mitad, pero no es así, simplemente la división consiste en buscar dentro de un rango en específico y ese rango es dado por el número que se encuentra a la mitad del arreglo. Sigamos. Como dijimos, buscaremos en los números que se encuentren antes que el número 11. Entonces nuestra búsqueda se realizará en este rango:

2,4,5,7,9,11

Realizamos la misma operación que se hizo en un principio. Se hará la comparación con el elemento central de esta lista.

2,4,5,7,9,11

¿Es 5 (nuestro número) igual a 5?

Si, si es igual. Entonces el número ha sido encontrado.

Es así como funciona la búsqueda binaria.

En el peor caso, utilizando la búsqueda binaria, la búsqueda en un arreglo de 1024 elemento solo tomará 10 comparaciones (2¹⁰) en cambio, en la búsqueda lineal, en el peor escenario, tomaría hacer 512 comparaciones para hallar el resultado. Si tuviésemos un arreglo de mil millones de elementos 2³⁰ , una búsqueda binaria en el peor de los casos tendría que hacer 30 comparaciones, en cambio la búsqueda lineal tendría que realizar por lo menos 500 millones de comparaciones. Esa es una gran diferencia en cuanto a rendimiento entre la búsqueda lineal  y la binaria.

El algoritmo de búsqueda que se comentó (2,4,5,7,9,11,13,15,17,21,25,30) puede ser implementado de la siguiente manera.

#include<stdio.h>

int main(void){

  int i, buscar, lista[100], mitad;

  int a = 0;

  int b = 100;

  int contadorA = 0;

  int contadorB = 0;

  printf("====================================================\n\n");

  //se llena el arreglo

  for( i = 0; i <= 100; i++){

    lista[i] = i * 2;

  }//fin for

//se muestra el arreglo en pantalla

  for(i = 0; i <= 100; i++){

    printf("%d  ", lista[i]);

    if( i % 10 == 0 && i != 0)

      printf("\n");

  }

  printf("\n\n====================================================\n");

  printf("Ingresa un numero a buscar: ");

  scanf("%d", &buscar);

  while (a <= b){

    contadorA++;

    mitad = (a + b) / 2;

    if(buscar > 200){

      printf("Numero no encontrado\n");

      break;

    }

    if(buscar == lista[mitad]){

      printf("Numero %d encontrado en posicion %d\n", lista[mitad], mitad);

      break;

    }

    else if(buscar < lista[mitad]){

      b = mitad -1;

    }

    else{

      a = mitad + 1;

    }

    contadorB++;

  }//fin while

if(contadorA == contadorB){

  printf("Numero no encontrado\n");

}

return 0;

}

Esto es todo por ahora, espero se haya entendido.

Gustavo J. Cerda Nilo

Agosto 2016, Octubre 2016