metodos de busqueda




FACULTAD DE CIENCIAS DE LA INGENIERÍA.
MÉTODOS DE BÚSQUEDA.
INTEGRANTES:
CUASPUD ANDERSON.
MAZON ANDRES.
ROBLES GENESIS.
VERGARA JOSELYN.
DOCENTE:
ING. IVÁN JARAMILLO.
ASIGNATURA:
ESTRUCTURA DE DATOS.
CARRERA:
INGENIERÍA EN SISTEMAS.
PERIODO LECTIVO 2015-2016







MÉTODOS DE BÚSQUEDA.
Búsqueda binaria.
Es una operación que tiene por objetivo la localización de un elemento dentro de laestructura de datos.
La búsqueda binaria consiste en dividir el intervalo de búsquedas en dos partes, comparando el elemento buscado con el que ocupa la posición central del arreglo, usando la técnica divide y vencerás.
Características:
Se utiliza para acortar el tiempo de búsqueda.
Los datos deben estar ordenados.
Procedimiento:
Ubica el elemento central del array sumando la 1era y 2da posición deeste y lo divide entre 2.
Ubicado el elemento central divide el array en dos (sub-arrays).
Identifica en que sub-array se encuentra el dato a buscar (derecha o izquierda).
Si el dato es menor al elemento central, usa el sub-array de la izquierda.
Si el dato es mayor al elemento central, usa el sub-array de la derecha.
Realiza el mismo proceso hasta encontrar el elemento buscado.

El algoritmo debúsqueda tiene una complejidad de O(log n).
Algoritmo:
int busquedaBinaria(int vector[], int n, int dato)
{
int centro,inf=0,sup=n-1;
while(inf<=sup){
centro=((sup-inf)/2)+inf;
if(vector[centro]==dato) return centro;
else if(dato < vector[centro]) sup=centro-1;
else inf=centro+1;
}
return -1;
}
Búsqueda Secuencial.
La búsquedasecuencial consiste en revisar todos (uno por uno) los elementos de un conjunto, hasta encontrar aquel que es buscado o hasta que se termine el recorrido del vector.
Una búsqueda secuencial puede tener dos posibles resultados:
El elemento buscado no está en el vector.
El elemento buscado si está en el vector, en este caso debe indicar la posición del vector en que se encuentra el elemento.
Lo bueno dela búsqueda secuencial es que no requiere que el conjunto esté previamente ordenado, pero como debe revisar todos los elementos se torna muy lenta.
Algoritmo:
int busquedaSimple(int vector[n], int n, int dato)
{

int i;

for(i=0; i if(dato==vector[i]) {
return i;
break;
}
}
return -1;
}

Búsqueda Fibonacci.
La técnica de Fibonaccies un método de búsqueda en un array ordenado usando la técnica divide y vencerás que disminuye las ubicaciones posibles con la ayuda de los números Fibonacci.
Comparando con la búsqueda binaria, Fibonacci busca las ubicaciones cuyas direcciones tienen poca dispersión. La búsqueda Fibonacci tiene una ventaja sobre la búsqueda binaria es disminuir ligeramente el tiempo promedio necesario paraacceder a la ubicación del almacenamiento.
La complejidad es O(log n).
Algoritmo:
Es un método mejorado al de búsqueda binaria. Se diferencia de ella en que la partición de los subarrays se realiza usando los números de Fibonacci.
Dado un array ordenado A y un elemento t, verificar si t está en A:
Sea F el array de los números de Fibonacci. Fm es el m-enésimo elemento de F. n es el tamaño A. Sea m talque Fm es el número más pequeño de F mayor o igual que n.
F es definido como: F0 = 1, F1 = 1, Fk = Fk-1 + Fk-2.
Para probar si t pertenece a A, seguir los siguientes pasos:






Reenumerar los elementos restantes de A, hacer k = k - 2 y volver al paso 2.
Implementación alternativa (de “Sorting and Searching” por Knuth): Dado una tabla de registros R1, R2,..., Rn cuyas llaves están en ordenincremental K1 < K2 <... < Kn, el algoritmo busca por un elemento K dado. Asumir n + 1 = Fk+1.
Paso 1. [Inicialización] i ← Fk, p ← Fk-1, q ← Fk-2 (durante el algoritmo, p y q serán números de Fibonacci consecutivos).
Paso 2. [Comparar] SI K < Ki, ir al paso 3; si K > Ki ir al paso 4; y si K = Ki, el algoritmo termina exitosamente.
Paso 3. [Decrementar i] Si q = 0, el algoritmo termina exitosamente....

Leer documento completo

Regístrate para leer el documento completo.