En el primer caso, sólo hay que recorrer el vector entero con ciclo. Vamos a ver ahora cómo acceder a un dato específico en un vector, mediante algoritmos de búsqueda.
Para ello, vamos a crear una función Buscar, que deberá recorrer el vector viendo si cada elemento del mismo coincide con el dato a buscar. Si el elemento coincide, la función debe devolver la posición del vector en la que está, si no coincide debe pasar a comparar el siguiente elemento. Si llego al final del vector sin haber encontrado un elemento igual al dato, significa que no hay un elemento igual en el vector. En este caso, la función deberá devolver -1 para que el programa sepa que no se encontró el dato.
int
buscar(long v[], int
tam, long elem)
{
int i;
for (i=0;
i<tam; i++)
{
if(v[i]== elem) return
i; // Si un elemento coincide, devuelve la posición.
}
// si llegó hasta acá, significa que terminó el ciclo sin
encontrarlo
return -1;
}
La función recibe como parámetros el vector, un int con la cantidad de elementos que tiene el vector y el dato a buscar, que es del mismo tipo de dato que el vector. Devuelve un int con la posición en que encontró el dato (o -1 si no lo encuentra).
Un programa que use la función, podría ser por ejemplo:
#include
<iostream>
using
namespace std;
#define
T 10
int
buscar (long [], int,
long );
void
main()
{
long
Padrones[T];
int
i,pos;
long pad;
// Cargo el vector
for (i = 0; i<T;i++)
{
cout
<<" Ingrese un padron:";
cin
>> Padrones[i];
}
cout
<< "Vector cargado."<<endl<<endl;
cout
<< "Ingrese el padrón que desea
buscar:";
cin
>> pad;
pos =
buscar (Padrones, T, pad);
if (pos != -1)
cout
<<"El elemento se encuentra en la posición
"<< pos <<endl;
else
cout
<<"El elemento no se encuentra en el
vector"<<endl;
cin
>> i;
}
Primero se carga el vector. Luego se le pide al usuario que ingrese un número de padrón, y se llama a la función buscar, pasándole ese número de padrón.
Si el valor que devuelve la función es -1, significa que el elemento no estaba en el vector, en caso contrario, devuelve la posición en la que está el padrón.
Este método de búsqueda, no es muy eficiente, si el elemento no está en el vector, tiene que comparar todos los elementos del vector para darse cuenta. Si el elemento está en el vector, depende de su posición: si el el primero, lo encuentra en una comparación; pero si el elemento es el último, tardará N comparaciones en encontrarlo. Si N es la cantidad de elementos del vector, se tardará en promedio N/2 comparaciones en encontrar el elemento.
Si queremos hacer la búsqueda más rápidamente, necesitamos que el vector esté ordenado. Así, en vez de empezar a comparar desde el principio, comparamos el dato con el elemento que está en la mitad del vector. Si el dato es menor al elemento medio del vector, ya podemos descartar toda la mitad superior del mismo. Si el elemento es mayor, descartamos la primera mitad del vector. Luego podemos llamar recursivamente a la función para que busque en el medio vector que le queda.
Así hasta que el elemento medio del vector sea igual al dato, o hasta que no quede sub-vector donde buscarlo. Esta búsqueda es mucho más rápida, ya que cada comparación permite descartar la mitad de los elementos del vector. Se puede comprobar que la cantidad de búsquedas a realizar es aproximadamente log2(n) / 2, lo que es mucho más rápido que n/2, y esa diferencia aumenta más cuanto más grande sea n.
int
buscar_binario(long v[], int desde, int hasta,
long elem)
{
int mitad;
if (desde > hasta)
return -1; // me
quedé sin vector donde buscar!!
mitad =
(desde+hasta) /2;
if (v[mitad] == elem) //Lo encontré
return
mitad;
else
if (v[mitad]< elem) //Debo buscar en
la segunda parte del vector, entre mitad+1 y hasta
return buscar_binario(v,mitad+1,hasta,elem);
else //Debo
buscar en la primera parte, entre desde y mitad-1
return buscar_binario(v,desde,mitad-1,elem);
}
La función tiene cuatro salidas posibles:
- Si los límites "desde" y "hasta" están cruzados (desde > hasta) significa que fui achicando el rango en el que buscar tanto que ya no me quedó vector donde buscar. Por lo tanto, el dato a buscar no está en el vector y devuelvo -1.
- Si el dato a buscar coincide con el elemento que está en la mitad del rango en el que busco, devuelvo la posición de esa mitad y termina la búsqueda.
- Si el dato a buscar es mayor que el elemento que está en la mitad del vector, debo buscar en el rango (mitad+1; hasta) del vector.
- Si el dato a buscar es menor que el elemento que está en la mitad del vector, debo buscar en el rango (desde; mitad-1) del vector.
El programa que llama a la función podría ser similar al anterior, sólo habría que asegurarse de ordenar el vector antes de llamar a la función, y modificar la llamada para que quede:
pos = buscar_binario (Padrones, 0, T-1, pad); //Desde = 0; Hasta = T-1
No hay comentarios:
Publicar un comentario