11/18/2005

Busqueda binaria en C++

La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:

int vector[10] = {2,4,6,8,10,12,14,16,18,20};

La clave que queremos buscar es 6. El algoritmo funciona de la siguien manera

  1. Se determinan un indice arriba y un indice abajo, Iarriba=0 e Iabajo=9 respectivamente.
  2. Se determina un indice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 4.
  3. Evaluamos si vector[Icentro] es igual a la clave de busqueda, si es igual ya encontramos la clave y devolvemos Icentro.
  4. Si son distintos, evaluamos si vector[Icentro] es mayor o menos que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurandonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 4 < 6, entonces la parte del arreglo vector[0...4] ya puede descartarse.
  5. Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos subir hasta 5, entonces quedaria Iarriba = 9, Iabajo = 5. Y volvemos al paso 2.

Si la clave no fuese encontrada en algun momento Iabajo > Iarriba, con un while vamos a controlar esta condición para salir del ciclo en tal caso y devolver -1 (clave no encontrada).

Hagamos modificaciones al código de busqueda lineal para implementar una función de busqueda binaria.


//Busqueda binaria
//en un arreglo.
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que
recibe un arreglo constante
int busquedaBinaria(const int[], int, int); //arreglo, tamano, clave
void ordenarArreglo(int[], int); //prototipo que modifica y ordena el
arreglo
void intercambiar(int&, int&); //prototipo, intercambia
los valores de dos elementos
int main()
{
  int clave =0;
  const int tamano = 15;
  int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78,21,10};
  //ordenamos el arreglo para que funcione la busquedaBinaria
  ordenarArreglo(arreglo,tamano);
  cout << "Elementos del arreglo: " << endl;
  mostrarArreglo(arreglo,tamano);
  cout << "Indique un valor a buscar y se le devolvera el indice: " << endl;
  cin >> clave;
  cout<< "Su valor se encuentra en arreglo["<<busquedaBinaria(arreglo,tamano,clave)<<"]" << endl;
  cout << "Fin del programa :)" << endl;
  return 0;
}//fin de main
void mostrarArreglo(const int arreglo[], int tamano)
{
  for (int i = 0 ; i < tamano ; i++)
    cout << "arreglo[" << i << "]=" << arreglo[i] << endl;
}
int busquedaBinaria(const int arreglo[], int tamano, int clave)
{
  int Iarriba = tamano-1;
  int Iabajo = 0;
  int Icentro;
  while (Iabajo <= Iarriba)
    {
      Icentro = (Iarriba + Iabajo)/2;
      if (arreglo[Icentro] == clave)
 return Icentro;
      else
 if (clave < arreglo[Icentro])
   Iarriba=Icentro-1;
 else
   Iabajo=Icentro+1;
    }
  return -1;
}
void ordenarArreglo(int arreglo[], int tamano)
{
  for (int i = 0; i< tamano -1 ; i++)
    for (int j = 0; j< tamano -1 ; j++)
      if (arreglo[j] > arreglo[j+1])
 intercambiar(arreglo[j],arreglo[j+1]);
}
void intercambiar(int &a, int &b)
{
  int tmp = b;
  b = a;
  a = tmp;
}

Ver como hacer para compilar este programa.

20 comentarios:

Anónimo dijo...

SOY ESTUDIANTRE DE LA CARRERA DE INGENIERIA DE SISTEMAS Y QUERIA SABER SI ME PODRIAN AYUDAR UN POCO CON LO QUE ES BUSQUEDA BINARIA ,A PODER DESARROLLAR UNA APLICACION SENCLLA. ayudenme

Anónimo dijo...

studio informatica eh chevere pero un poco mas struct ok.

Anónimo dijo...

soy estudiante de ingenieria en informatica quiesiera implementar la busqueda terciaria...
ayudenme

Anónimo dijo...

Soy estudiante de 4º año de ingeniería de sistemas y estaba tratando de encontrar el algoritmo que había estudiado hace ya bastante. Si bien no reparé en la implementación del código del algoritmo, la descripción de este no es la correcta.

En primer término si el arreglo contiene 10 elementos los índices arriba y abajo deberían ser 0 y 9 respectivamente dado que si se hiciera de la otra manera (0 y 10) se estarían conteniendo 11 elementos.

En segundo lugar si lo que se desea es ubicar el elemento 6, lo que se debe comparar en el punto 4 sería si Arreglo[centro] es menor o mayor que 6, en este caso, Arreglo[4]=10. De esta manera, dado que 6 es menor que 10, lo que se debe eliminar es la segunda parte del arreglo (Arreglo[5...9]) y no la primera, quedando en este caso arriba=0 y abajo=4 para comenzar de vuelta con el algoritmo.

Saludos.

Anónimo dijo...

En realidad quedaría (cuando se vuelva nuevamente al paso 2) arriba=0 y abajo=3. Si no se hiciera de esta manera (que cuando se busca en la primera parte, abajo=centro-1 y cuando se busca en la segunda parte arriba=centro+1) existiría la posibilidad de que el algoritmo se quede ciclando infinitamente.

Saludos.

Anónimo dijo...

soy hector y estudio la lic en sistemas computacionales quiero saber sobre la busqueda binaria por que no le entiendo me podrian ayudar como hacer un programa y tambien con arreglos

Moy dijo...

MOY
Soy estudiante de Mecatronica de mexico y quiero hacer una programa en Visual Studir en un vo 20005, para busca en un vector de 100 elementos!!!

Espero su apreciable ayuda!!!
Contactenme

Anónimo dijo...

hola estudio ingenieria en sisetamas computacionales, me gustaria saber mas hacerca de busqeud binaria, bueno como se lleva acaboel programa en areglos, y un poco de informacion de lo que es en si el temas de busqeuda binaria, gracias amigos saludos gabriel

Anónimo dijo...

hola me llamo sergio soy estudiante de la carrera de licenciatura en informatica y quisiera desirles que todos se vallan al infierno y que se pudran jajajajajajajajajajajajaja

andres nieto dijo...

hola q tal soy estudiante me parece q esa tipo de busqueda es sumamente potente a la hora de localizar un elemento, y el estupido de arriba es un idiota!! ese debe estudiar bagologia intensa!!! cabeza de crap!.

Anónimo dijo...

HOLA SOY ESTUDIANTE DE SISTEMAS DE INFORMACIÓN Y ME GUSTARÍA SABER COMO SE REALIZARÍA LA PRUEBA DE ESCRITORIO CON EL EJERCICIO QUE ESTA EN LA PORTADA CON 10 PASOS

Jukka dijo...

soy estudiante de primer año de ing electrica y todos son unos copiones!, si esta bn, le falla en algo pekeño

jose dijo...

hola soy estudiante de secundaria y necesito implementar un simpre programa de busqueda binaria que adivine el numero que piensa una persona porfa si alguen me puede ayudar escribanme a j.o.s.e.flameboy@hotmail.com

Anónimo dijo...

xajil: estudio ingeneria en sistemas y de proyecto ,ay que desarroyar un programa donde se implementen tres metodos de ordenamientos ,que con tenga un menu para elegir el metodo de ordenamiento que se quere ,que incluya datos numericos y alfa numericos y tambien dentro ese programa se implementen dos metodos de busquedas :
y no encuentro la manera de acerlo ,me podrian ayudar

Anónimo dijo...

No entendi muy bn me colaboran con otro ejemplo

Anónimo dijo...

OYEME TU HIJO DE PUTA PORQUE PUTAS MADRES USAS PRINTF Y SCANF SI NO LOS SE USAR PENDEJO!!!!!

Anónimo dijo...

pero si el printf y el scanf sobn mas rapidos que el cin y el cout

Aristides Sequeira dijo...

no le entendí nada a la explicación y creo que fuera bueno que hicieras oto ejemplo usando la librería "stdafx.h" o "stdio.h" que son mas fáciles de usar y comprender

Anónimo dijo...

Pues si son estudiantes de ingeniería deberían poder hacer sus propias soluciones, buscar ayuda es bueno, pero no todo el código ._.

Anónimo dijo...

Hola soy Gokú y quiero aprender a hacer la Henkidama aumentada 10 ceces