ciencias

Fundamentos de Programación - Búsquedas

Página 1

Tipos de búsquedas
• Internas
(Vectores) Se realizan en la memoria del computador
• Externas
(Archivos) Se realizan en dispositivos externos, tales
como, medios magnéticos.

FUNDAMENTOS DE
PROGRAMACIÓN

Búsquedas

Master Jorge Lombeida Chávez

1

Métodos de búsquedas

Master Jorge Lombeida Chávez

2

Búsquedassecuenciales

• Secuenciales
(preguntar por cada uno de los elementos en
secuencia, desde el primero, luego por el segundo,
por el tercero y así sucesivamente hasta el final)
• Aleatorias
(preguntar por un elemento elegido al azar y luego
por otro también elegido al azar y así sucesivamente
hasta haber evaluado todos)

• Tres métodos de búsquedas
N = Dimensión de la tabla
I = indice para barrerla tabla
Vector
I=1

1

16

I=2

2

31

I=3

3

29

I=4

4

28

I=5

5

15

Valor 28

¿ Vector (I) = valor ?

N=5
Master Jorge Lombeida Chávez

Master Jorge Lombeida Chávez

3

Búsqueda Secuencial
Primer Método

Búsqueda Secuencial
Búsqueda
Primer Método Secuencial
Primer Método
Inicio
I := 1
I>N
++I

• Exagerado número de preguntas
#preguntas = 2 N + 1
• En cada ciclo se pregunta si I es mayor que N, y si
Vector (I) es igual a valor

No se
encuentra

V
F

Vector (I)
= Valor

V

Está en la
posición, I

I=1
Fin

I=2
I=3

F

I=4
I=5

Master Jorge Lombeida Chávez

Master Jorge Lombeida Chávez

4

5

Vector
1

16

2

31

3

29

4

28

5

15
N=5

Valor 28

I>N
¿ Vector (I) =valor ?

Master Jorge Lombeida Chávez

6

EDCOM-ESPOL

Fundamentos de Programación - Búsquedas

Página 2

Búsqueda Secuencial
Segundo Método

Búsqueda Secuencial
Segundo Método

• Asegurar que el valor a buscar se encuentre dentro de la
tabla
• Aumentar un elemento temporalmente al final del vector
para ubicar el valor de búsqueda
• El valor de búsqueda se encontrará, ódentro de los N
elementos de la tabla, ó, en el elemento N+1
1

4
5

3

29

4

28

4

28

5

15

5

15

N=5

28

29

6

21

Valor 21

15

6

31

3

28

15
N=5

2

29

28

16

31

31

3

1

16

2

16

2

Vector

Vector

Vector

Vector
1

1

16

2

31

3

29

4
5

Valor 28

Master Jorge Lombeida Chávez7

Master Jorge Lombeida Chávez

Búsqueda Secuencial
Segundo Método

Búsqueda Secuencial
Búsqueda
Segundo Método Secuencial
Inicio
Segundo Método

• Se reduce el número de preguntas
# preguntas = N + 2
• En cada ciclo se pregunta sólo si Vector (I) es igual
a valor

Vector (N + 1) := Valor
I := 1

Vector (I)
= Valor

V

I≤N

V

Está en la
posición, I

Vector++ I

1

Master Jorge Lombeida Chávez

28

5

15

6
9

29

4
Fin

31

3

F
No se
encuentra

16

2
F

8

28

Valor 28

¿ Vector (I) = valor ?

Master Jorge Lombeida Chávez

Búsqueda Secuencial
Tercer Método

10

Búsqueda Secuencial
Tercer Método

• Se aplica a tablas ordenadas ascendentemente
• Se reduce el número de preguntas al mantener unordenamiento
• Aumentar un elemento temporalmente al final
del vector para ubicar el valor más grande posible

Vector

¿ Valor > Vector (I) ?
Vector

Vector

1

16

1

15

1

15

2

31

2

16

2

16

3

29

3

28

3

28

4

28

4

29

4

29

5

15

5

31

5

31

N=5

6

999

N=5

Valor 28

Un número lo más
grande posibleMaster Jorge Lombeida Chávez

Master Jorge Lombeida Chávez

11

Master Jorge Lombeida Chávez

12

EDCOM-ESPOL

Fundamentos de Programación - Búsquedas

Página 3

Búsqueda Secuencial
Tercer Método
¿ Valor > Vector (I) ?

Inicio

16

3

28

4
5
6

Vector

15

2
Valor 21

Vector (N + 1) := 999

¿ Valor > Vector (I) ?

Vector
1

Búsqueda Secuencial...