Busqueda Binaria/lineal

DICIEMBRE 2012

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.

{

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;

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.

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

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

A = 1 11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=1

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

A = 1 11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=2

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

A = 1 11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=3

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

A = 1 11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=4

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

A = 1 11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=5

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

A = 1 11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=6

Note que si el valor NO se encuentra en el arreglo, entonces se recorre todo el arreglo, posición aposició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 más 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

Valor a buscar en el arreglo A: VALOR = 75

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

A = 1 11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=1

...