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 Beatriz Serrano V. 4/11

Computación II

COMO LOGRARLO:

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

 Determinar la posición media del arreglo

 Mientras el elemento en la posición media sea diferente de VALOR

ejecute:

o Descartar una mitad del arreglo

o Determinar el nuevo rango:

como la otra mitad

o Determinar el punto medio del nuevo rango

 Determinar si encuentra o no el

VALOR

 Encuentra VALOR en el arreglo cuando aborta el proceso de búsqueda.

 No encuentra VALOR cuando termina la búsqueda.

{

Proceso de Búsqueda Binaria de VALOR en el arreglo X

}

{ Inicializaciones }

m := N div 2 + 1;

i := 1;

j := N;

{ Recorrido del arreglo buscando VALOR } While ( ( A[ m ] <> VALOR ) and ( i <= j )) do

begin

if A[m] > VALOR then j := m – 1

else

i := m + 1;

m := ( i + j ) div 2 + 1;

end;

{ Determinar si encontró o no } If A[m] = VALOR then

POS := m;

Algunas Aplicaciones

UNION DE ARREGLOS UNIDIMENSIONALES

C  A ∪ B

La unión de dos arreglos se determina generando un nuevo arreglo con los elementos de ambos arreglos. Esta es una de las aplicaciones que requieren de la búsqueda lineal para la generación del nuevo arreglo. Es importante destacar que se agregara [insertara al final del arreglo] un valor siempre y cuando este no exista ya en el arreglo.

Por ejemplo:

Dados los arreglos A y B, para determinar la unión de ambos es necesario generar un nuevo arreglo, C, con los elementos de ambos arreglos. Nota: el nuevo arreglo, C, no debe contener

elementos repetidos.

Asumiendo que A y B almacenan los elementos que se especifican a continuación y que han sido declarados y leídos previamente.

A =

B =

El vector unión seria:

C =

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

Computación II

Para realizar esta tarea es necesario recorrer ambos arreglos y determinar que el elemento a agregar en el nuevo arreglo NO exista ya en él.

Observe que la dimensión del nuevo arreglo, C, NO es la suma de las dimensiones de los arreglos procesados, A y B, por lo que se requiere de una variable auxiliar que represente esta dimensión.

Los pasos a seguir para determinar la unión de dos arreglos son:

 Recorrer el primer arreglo

 Buscar que NO esté en C para ser insertado en C

 Recorrer el segundo arreglo

 Buscar que NO esté

...