Semana09 AED 15592

Búsquedas en Arreglos

Búsqueda de un elemento

La búsqueda de un elemento es la
determinación de la localidad de un
elemento con ciertas características.

Métodos de Búsqueda
– Búsquedasecuencial
– Búsqueda binaria

Búsqueda secuencial
El método de búsqueda secuencial
compara cada elemento del arreglo
buscando un elemento correspondiente.

Búsqueda secuencial
int secuencial(int arreglo[],int n, int valor) {
int indice = -1;
for (int i = 0 ; i < n ; i++) {
if ( arreglo[i] == valor) {
indice = i;
break;
}
}
return indice;
}

Búsqueda binaria
•

Los prerrequisitos principales para labúsqueda binaria son:

– La lista debe estar ordenada en un orden especifico
de acuerdo al valor de la llave.
– Debe conocerse el número de registros.

Búsqueda binaria
• Pasos
1. Se compara la llavebuscada con la llave localizada al centro
del arreglo.
2. Si la llave analizada corresponde a la buscada fin de
búsqueda si no.
3. Si la llave buscada es menor que la analizada repetir proceso
en mitadsuperior, sino en la mitad inferior.
4. El proceso de partir por la mitad el arreglo se repite hasta
encontrar el registro o hasta que el tamaño de la lista
restante sea cero , lo cual implica que elvalor de la llave
buscada no esta en la lista.

Búsqueda binaria
int binaria( int arreglo[], int n, int dato) {
int inicio = 0; int fin = n - 1;
int pos;
while (inicio <= fin) {
pos = (inicio+fin) /2;
if ( arreglo[pos] == dato )
return pos;
else
if ( arreglo[pos] < dato ) {
inicio = pos+1;
}
else {
fin = pos-1;
}
}
return -1;
}

Ejemplo de Búsquedas
Se tiene un arreglo ordenado de 19 númerosBuscar el número 107.
¿En que posición del arreglo se encuentra?
¿Cuántas comparaciones se hacen?

Búsqueda Secuencial
Posición = 16
Comparaciones = 17

Búsqueda Binaria
Posición = 16
Comparaciones = 3Búsqueda secuencial Vs. Búsqueda binaria
• La búsqueda secuencial requiere en promedio del orden de
n comparaciones, mientras que la búsqueda binaria
requiere del orden de log 2n.
• Ciertamente...