Búsqueda binaria

---

Buscar.h

#pragma once

class Buscar
{
private:
void intercambio(int [],int,int);
public:
int buscar(int[],int,int);
int *ordenarArreglo(int[],int);

};

---

Buscar.cpp


#include "StdAfx.h"
#include "Buscar.h"

int *Buscar::ordenarArreglo(int V[],int n)
{
for(int i=0;i<n-1;i++)
for(int j=i;j<n;j++)
if(V[i]>V[j])
intercambio(V,i,j);

return V;
}

void Buscar::intercambio(int V[],int i, int j)
{
int t;

t=V[i];
V[i]=V[j];
V[j]=t;
}


int Buscar::buscar(int V[],int n,int dato)
{
ordenarArreglo(V,n);

int mitad,izq,der;
izq=0;
der=n-1;

//el elemento que esta ala izquierda debe de ser menor que el de la derecha
while(izq<=der)
{
//calculamos el elemento central del arreglo hasta encontrar el valor buscado
mitad=(izq+der)/2;
//si el elemento buscado es mayor que el centro entonces buscamos en la segunda mitad del arreglo
if(dato>V[mitad])    
izq=mitad+1;//el primer valor del arreglo pasa hacer la mitad mas 1
else
//si el elemento buscado buscado es menor que la mitad entonces buscamos en la primera mitad del arreglo
if(dato<V[mitad])
der=mitad-1;
else
return mitad; //retornamos el elementoencontrado  
}
return -1;//el elemento no existe en el arreglo}
}

---

Descargar toda la solución de Clases en C++ para abrir con Visual Studio 2010

Busqueda binaria

Realiza la búsqueda binaria

---

#include "stdafx.h"
#include "iostream"
#include "conio.h"
#include "string"
using namespace std;

void ordenarvector(string *E,int n)
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(E[i]>E[j])
{
string aux=E[i];
E[i]=E[j];
E[j]=aux;
}
}
}
}

int busquedaBinaria(string *E,int n, string nombreBuscado)
{
int Iarriba=n-1,Iabajo=0,Icentro;

while (Iabajo <= Iarriba)
{
Icentro = (Iarriba + Iabajo)/2;
if (E[Icentro] == nombreBuscado)
return Icentro;
else
if (nombreBuscado<E[Icentro])
Iarriba=Icentro-1;
else
Iabajo=Icentro+1;
}
return -1;
}

void mostrarVector(string *E,int n)
{
for(int i=0;i<n;i++)
cout<<i+1<<": "<<E[i]<<endl;
}


void main()
{
int n;

string nombreBuscado;

cout<<"Ingrese cantidad de nombres: ";cin>>n;

string *names = new string[n];

for(int i=0;i<n;i++)
{
cout<<"Nombre "<<i+1<<": ";
cin>>names[i];
}

ordenarvector(names,n);
cout<<endl<<"Vector ordenado : "<<endl;
mostrarVector(names,n);

cout<<endl<<"Ingrese el nombre de un alumno a buscar: ";cin>>nombreBuscado;

int index=busquedaBinaria(names,n,nombreBuscado);

if(index == -1)
cout<<"No se encuentra el nombre";
else
cout<<"Encontrado en el indice "<<index+1;

_getch();
}