MÉTODOS DE BUSQUEDA

Métodos de Búsqueda

Búsqueda Secuencial / Lineal

Esta práctica tiene como objetivo principal ejercitar la manipulación de arreglos unidimensionales, así como también reforzar las técnicas de depuración y el análisis de programas.

BÚSQUEDA SECUENCIAL / LINEAL

El proceso de búsqueda secuencial es una de las operaciones más comunes en la manipulación de arreglos. Puede definirse como el proceso de determinar el elemento, o su posición, que cumple

una condición, comparando con cada uno de los elementos en forma secuencial. Es el método de

búsqueda recomendado cuando se tiene un arreglo en el cual no se conoce la relación entre sus elementos, es decir estos están desordenados.

QUE SE TIENE:

Para llevar a cabo esta tarea se requiere de la siguiente información de entrada:

 El arreglo

 La dimensión del arreglo

 La condición: el valor a buscar

QUE SE PIDE:

Determinar La posición POS donde se encuentra VALOR en el arreglo A.

Note que tiene dos posibles resultados:

 Encontrar VALOR en A

 No encontrar VALOR en A

COMO LOGRARLO:

Para llevar a cabo esta tarea se requiere de tres pasos:

 Asumir que VALOR no se encuentra en el arreglo

 Recorrer el arreglo hasta encontrar o

no encontrar VALOR en el arreglo

 Determinar si encontró o no el

VALOR:

 Encuentra VALOR en el arreglo cuando termina la búsqueda y no ha terminado de recorrer todo el arreglo. En este caso POS almacena la posición donde se encuentre VALOR en X.

 No encuentra VALOR en el arreglo, En este caso termina de recorrer el arreglo. POS almacena la posición donde se encuentre VALOR en X. Quedando POS con el valor cero.

{

Proceso de Búsqueda Secuencial de VALOR en el arreglo A

}

{ Inicializaciones } POS := 0;

I := 1;

{ Recorrido del arreglo buscando VALOR } While ( ( I< = N ) and

( A[ I ] <> VALOR ) ) do

I := I + 1;

{ Determinar si encontró o no } If I <= N then

POS := I;

Prof. María Beatriz Serrano V. 1/11

Computación II

Ejemplo de Búsqueda Secuencial: Valor a buscar en el arreglo A: VALOR = 33

Primera iteración: A[1]=1 <> VALOR

A =

i=1

Segunda iteración: A[2]=11 <> VALOR

A =

i=2

Tercera iteración: A[3]=21 <> VALOR

A =

i=3

Cuarta iteración: A[4]=25 <> VALOR

A =

i=4

Quinta iteración: A[5]=26 <> VALOR

A =

i=5

Sexta iteración: A[6]=33 = VALOR

A =

i=6

Note que si el valor NO se encuentra en el arreglo, entonces se recorre todo el arreglo, posición a posición hasta agotar los elementos. En este caso, siempre se cumple que A[i] <> VALOR.

Búsqueda Binaria

La búsqueda binaria permite buscar valores mas eficientemente que la búsqueda secuencial, sin embargo, el método requiere que la información sobre la cual se va a buscar este ordenada.

El método se basa en el conocimiento de la información. Al estar ésta ordenada puede descartarse la mitad que se sabe no es posible que este la información. Veamos algunos ejemplos:

Prof. María Beatriz Serrano V. 2/11

Computación II

EJEMPLO 1: CASO EN QUE NO SE ENCUENTRA EL VALOR

Valor a buscar en el arreglo A: VALOR = 75

Primera iteración: A[m]=59 <> VALOR

A =

i=1 m=13 j=25

VALOR > A[m] se descarta la primera mitad

Segunda iteración: A[m]=77 <> VALOR

A =

i=14 m=20 j=25

VALOR < A[m] se descarta la segunda mitad

Tercera iteración: A[m]=67 <> VALOR

A =

i=14 m=17 j=19

VALOR > A[medio] se descarta la primera mitad

Cuarta iteración: A[m]=72 = VALOR

A =

i=18 m=19 j =19

VALOR > A[medio] se descarta la primera mitad

Quinta iteración: A[m]=76 = VALOR

A =

j=19 i=20 m=19

Termina la búsqueda, VALOR NO se encuentra en posición: m; i > j

Prof. María Beatriz Serrano V. 3/11

Computación II

EJEMPLO 2: CASO EN QUE SE ENCUENTRA EL VALOR

Valor a buscar en el arreglo A: VALOR = 48

Primera iteración: A[m]=59 <> VALOR

A =

i=1 m=13 j=25

VALOR < A[m] se descarta la segunda mitad

Segunda iteración: A[m]=38 <> VALOR

A =

i=1 m=7 j=12

VALOR > A[m] se descarta la primera mitad

Tercera iteración: A[m]=50 <> VALOR

A =

i=8 m=11 j=12

VALOR < A[m] se descarta la segunda mitad

Cuarta iteración: A[m]=48 = VALOR

A =

i=8 m=10 j=10

Termina la búsqueda, VALOR se encuentra en posición: m

BÚSQUEDA BINARIA: INSTRUCCIONES:

QUE SE TIENE:

Para llevar a cabo esta tarea se requiere de la siguiente información de entrada:

 El arreglo ORDENADO

 La dimensión del arreglo

 La condición: el valor a buscar

QUE SE PIDE:

Determinar La posición POS donde se encuentra VALOR en el arreglo X.

Note que tiene dos posibles resultados:

 Encontrar VALOR en X

 No encontrar VALOR en X

Prof. María

...