Metodos de busqueda

Métodos de Búsqueda
Búsqueda Secuencial / Lineal
Esta practica 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 dedeterminar 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 • Ladimensió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 noencontrar 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 valorcero.

{ 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 A[m] Segunda iteración: A[m]=77 VALOR A=
1

m=13 se descarta la primera mitad

j=25

11 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 8688 92 94 97

i=14 VALOR < A[m] Tercera iteración: A[m]=67 VALOR A=
1

m=20

j=25

se descarta la segunda mitad

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=14 VALOR > A[medio] Cuarta iteración: A[m]=72 = VALOR A=
1

m=17

j=19

se descarta la primera mitad

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

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

m=19 j =19 se descarta la primera mitad

i=18

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

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. Computación II

3/11

EJEMPLO 2: CASO EN QUE SE ENCUENTRA EL VALOR Valor a buscar en el arreglo A: VALOR = 48Primera 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 VALOR < A[m] Segunda iteración: A[m]=38 VALOR A=
1

m=13 se descarta la segunda mitad

j=25

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

m=7 VALOR > A[m]

j=12 se descarta la primera mitad

Tercera iteración: A[m]=50 VALOR A=
111 21 25 26 33 38 40 42 48 50 56 59 60 62 64 67 72 76 77 86 88 92 94 97

i=8 VALOR < A[m] Cuarta iteración: A[m]=48 = VALOR A=
1

m=11

j=12

se descarta la segunda mitad

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

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 tarease 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

i=8

Prof. María Beatriz Serrano V. Computación II

4/11

COMO LOGRARLO: Para...