Algoritmos de Búsqueda

// Algoritmo de Búsqueda Binaria Iterativa

void BinarySearch(Elemento A[], int First, int Last, Elemento Value, int &r) {

int Mid = (First + Last)/2;

while (First <= Last && Value != A[Mid]) {

if (Value < A[Mid]) Last = Mid-1;

else First = Mid+1;

Mid = (First + Last)/2;

}

if (Value == A[Mid]) r = Mid;

else r = -1;

}

// Algoritmo de Búsqueda Binaria Recursiva

void BinarySearchR(Elemento A[], int First, int Last, Elemento Value, int &r) {

int Mid = (First + Last)/2;

if (First > Last) r = -1;

else {

if (Value == A[Mid]) r = Mid;

else

if (Value < A[Mid])

BinarySearchR(A,First,Mid-1,Value,r);

else

BinarySearchR(A,Mid+1,Last,Value,r);

}

}

// Algoritmo de Búsqueda Secuencial

void SequentialSearch(Elemento X[], int Last, Elemento Value, int &r) {

int i = 0;

while (i < Last) {

if (X[i]==Value)

r = i;

i++;

}

}

// Algoritmo de Búsqueda Secuencial Mejorada

void ImprovedSequentialSearch(Elemento X[], int Last, Elemento Value, int &r) {

int i = 0;

r = -1;

while (r == -1 && i < Last) {

if (X[i]==Value)

r = i;

else

i++;

}

}

// Algoritmo de Búsqueda Secuencial Ordenada

void SequentialSearchOrdenada(Elemento X[], int Last, Elemento Value, int &r) {

int i = 0;

r = -1;

while (r == -1 && i < Last && X[i]<=Value) {

if (X[i]==Value)

r = i;

else

i++;

}

}

// Algoritmo de Búsqueda Binaria Iterativa

Int busquedaBinaria(T x, T v[], intcant)

{

intbajo=0, alto=cant-1, mitad, encontrado=0;

while((bajo<=alto)&&(!encontrado))

{

mitad=(alto+bajo)/2;

if(x==v[mitad])

encontrado=1;

else

if(x<v[mitad])

alto=mitad-1;

else

bajo=mitad+1;

}

return(encontrado?mitad:-1);

}

//Algoritmo de Búsqueda Binaria Recursiva

int busquedaBinaria(T A[], int valor, inferior, superior) {

if (superior < inferior)

return -1 // no encontrado o vector desordenado;

int m = inferior + ((superior - inferior) / 2);

if (A[m] > valor)

return busquedaBinaria(A, valor, inferior, m-1);

else

if (A[m] < valor)

return busquedaBinaria(A[], valor, m+1, superior);

else

returnm; //posicion del elemento encontrado

}

// Algoritmo de Árbol Binario de Búsqueda

bool estaEnABB(ArbolBin<tipo> &a, Nodo<tipo> *r, tipo x)

{

bool result=false;

while(r!=NULL && result==false)

if (a.recuperar(r)==x)

result=true;

else

if (a.recuperar(r)>x)

result=estaEnABB(a,*a.hijoIzq(r),x);

else

result=estaEnABB(a,*a.hijoDer(r),x);

return result;

}

// Algoritmo de Hashing Cerrado con Direccionamiento Abierto

int hashingDireccionamientoAbierto (T clave)

{

int i, last, posicion=-2;

if (n>>0)

{

for (i=hash(clave), last=(i-1+B)%B; i!=last && hashtab[i].estado != vacio && posicion==-2; i=(i+1)%B)

if (hashtab[i].estado != descartado)

if (hashtab[i].clave == clave)

posicion=I;

if (posicion == -2)

...