Algoritmos de Búsqueda

TEMA XIII: Algoritmos de Búsqueda y Ordenación

Programación I

Indice Búsqueda Automática de Información Búsqueda en un Vector

Recorrido con Tratamiento Selectivo Vector Ordenado Concepto de Campo Clave

Búsqueda Secuencial Búsqueda Secuencial con Centinela Búsqueda Binaria o Dicotómica Medida de la Complejidad de un Algoritmo

Valores del mejor, peor y caso medio Comparación de las Estrategias de Búsqueda

4

Búsqueda Automática de Información

Importancia en diferentes aplicaciones

Objetivo: Localización de un elemento clave dentro de una colección de datos

Búsqueda lineal Búsqueda Interna: Vectores,

Listas Búsqueda Externa: Ficheros

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

5

Búsqueda en un Vector

Tipos de BúsquedaBúsqueda SecuencialBúsqueda Binaria

Eficiencia vs generalidad Simplificación

Tipo índice numérico incrementos del índice - función succ

Tipo base simple comparaciones - función que realice la

comparación

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

6

Recorrido de un Vector con Tratamiento Selectivo

Recorrido completo del vector Localiza buscado n veces Código ejemplo:

VARbuscado: <tipo>;V: ARRAY [1..n] OF <tipo>;i: 1..n;

BEGINFOR i:=1 TO n DO IF V[i] = buscado THEN

(* procesar (v[i]) *)

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

7

Vector Ordenado

Vector ordenado por clave Si buscado en el vector no es

necesario recorrido completo Aumenta la eficiencia de búsqueda

Estrategias de Búsqueda Búsqueda Secuencial

Finaliza si componente >= buscado Búsqueda Binaria o Dicotómica

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

8

Concepto de Campo Clave

Clave: Valor que caracteriza al elemento que se busca Valor de un campo (clave simple)

Un elemento del vector Un campo de un elemento del vector

Combinación de varios (clave compleja)

Comparaciones con respecto a la clave

Clave compleja No comparación directa Función de comparación

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

9

Búsqueda Secuencial

Aplicable si: buscado solo una vez en el vector Sólo interesa la primera aparición

No siempre recorrido completo No imprescindible vector ordenado La búsqueda finaliza si:

Aparece buscado Se acaba el vector (buscado no está)

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

10

Búsqueda SecuencialCONST

n = …;VAR

buscado: <tipo>;V: ARRAY [1..n] OF <tipo>;

i: 1..(n+1);pos: 1..n;encontrado: BOOLEAN;

i := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO

BEGINi := i + 1;

encontrado := (buscado = V[i]);

END;IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

11

Ejemplo valor encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 4

12

Ejemplo valor encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 4

1

13

Ejemplo valor encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 4

1 F

14

Ejemplo valor encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 4

1 F

2 F

15

Ejemplo valor encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 4

1 F

2 F

3 T

16

Ejemplo valor encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 4

1 F

2 F

3 T

3

17

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

18

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1

19

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

20

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

21

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

3 F

22

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

3 F

4 F

23

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

3 F

4 F

5 F

24

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

3 F

4 F

5 F

6 F

25

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

3 F

4 F

5 F

6 F

7 F

26

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

3 F

4 F

5 F

6 F

7 F

8 F

27

Ejemplo valor no encontradoi := 1;encontrado := (buscado = V[i]);WHILE (i <= n) AND (NOT encontrado) DO BEGIN

i := i + 1;encontrado := (buscado = V[i]);

END;IF encontrado THEN pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus i enc pos

10 3 4 11 7 1 2 7 5

1 F

2 F

3 F

4 F

5 F

6 F

7 F

8 F

28

Vector OrdenadoCONST

n = ...;VAR

buscado: <tipo>; V: ARRAY [1..n] OF <tipo>;pos: 1..(n+1);encontrado, hallado: BOOLEAN;

pos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THENencontrado := (buscado = V[pos])

ELSEencontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

29

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

30

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

1

31

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

1 F

32

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

1 F

2

33

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

1 F

2

3

34

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

1 F

2

3

4

35

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

1 F

2

3

4 T

36

Ejemplo valor encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 4

1 F

2

3

4 T

T

37

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

38

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1

39

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1 F

40

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1 F

2

41

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1 F

2

3

42

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1 F

2

3

4

43

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1 F

2

3

4

5

44

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1 F

2

3

4

5 T

45

Ejemplo valor no encontradopos := 1;hallado := FALSE;WHILE (pos <= n) AND NOT hallado DO

IF buscado <= V[pos] THENhallado := TRUE

ELSEpos := pos +1;

IF (pos <= n) THEN encontrado := (buscado = V[pos])ELSE encontrado := FALSE;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

V[1] V[2] V[3] V[4] V[5] V[6] V[7] n bus pos hal enc

1 2 3 4 7 10 11 7 5

1 F

2

3

4

5 T

F

46

Búsqueda Secuencialcon Centinela

Dos Comparaciones no Eficiente Si buscado en el vector

Una comparaciónUn elemento más en el vector

Centinela

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

47

Búsqueda Secuencialcon Centinela

CONSTn = ...;

VARbuscado: <tipo>; V: ARRAY [1..(n+1)] OF <tipo>;i: 1..(n+1);pos: 1..n;encontrado: BOOLEAN;

i := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

48

Ejemplo valor encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 4

49

Ejemplo valor encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 4

1

50

Ejemplo valor encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 4

4 1

51

Ejemplo valor encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 4

4 1

2

52

Ejemplo valor encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 4

4 1

2

3

53

Ejemplo valor encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 4

4 1

2

3

T

54

Ejemplo valor encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 4

4 1

2

3

T

3

55

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

56

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

1

57

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

58

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

59

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

60

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

4

61

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

4

5

62

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

4

5

6

63

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

4

5

6

7

64

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

4

5

6

7

8

65

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

4

5

6

7

8

F

66

Ejemplo valor no encontradoi := 1;V[n+1] := buscado;WHILE (V[i] <> buscado) DO

i := i +1;encontrado := (i < (n+1));IF encontrado THEN

pos := i;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] n bus i enc pos

10 3 4 11 7 1 2 7 5

5 1

2

3

4

5

6

7

8

F

67

Búsqueda Binaria o Dicotómica

Sólo vectores ordenados Vectores grandes Cada iteración divide por la

mitad la zona de búsqueda

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

1 2 ............. n/2 ..................... n

izda medio der

?

68

Búsqueda Binaria o Dicotómica

Sólo vectores ordenados Vectores grandes Cada iteración divide por la

mitad la zona de búsqueda

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

1 2 ............. n/2 ..................... n

izda medio der

>=

69

Búsqueda Binaria o Dicotómica

Sólo vectores ordenados Vectores grandes Cada iteración divide por la

mitad la zona de búsqueda

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

1 2 ............. n/2 ..................... n

izda medio der

?

70

Búsqueda Binaria con comparación de igualdad Si V[medio] = buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

71

izda medio der

=

Búsqueda Binaria con comparación de igualdad Si V[medio] = buscado

Si V[medio] > buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

72

izda medio der

izda medio der

=

>

Búsqueda Binaria con comparación de igualdad Si V[medio] = buscado

Si V[medio] > buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

73

izda medio der

izda medio der

=

>

Búsqueda Binaria con comparación de igualdad Si V[medio] = buscado

Si V[medio] > buscado

Si V[medio] < buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

74

izda medio der

izda medio der

izda medio der

=

>

<

Búsqueda Binaria con comparación de igualdad Si V[medio] = buscado

Si V[medio] > buscado

Si V[medio] < buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

75

izda medio der

izda medio der

izda medio der

=

>

<

Búsqueda Binaria con comparación de igualdad

CONSTn = ...;

VARbuscado: <tipo>; V: ARRAY [1..n] OF <tipo>;izda, der: 0..(n+1);pos, medio: 1..n;encontrado: BOOLEAN;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

76

Búsqueda Binaria con comparación de igualdad

izda := 1;der := n;encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO

BEGINmedio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN

der := medio – 1ELSE

izda := medio + 1END;

IF encontrado THENpos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

77

Ejemplo valor encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1ELSE izda := medio + 1

END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

78

Ejemplo valor encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1ELSE izda := medio + 1

END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7 F

79

Ejemplo valor encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1ELSE izda := medio + 1

END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7 F

5 4 F

80

Ejemplo valor encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1ELSE izda := medio + 1

END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7 F

5 4 F

5 6 F

81

Ejemplo valor encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1ELSE izda := medio + 1

END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7 F

5 4 F

5 6 F

5 T

82

Ejemplo valor encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1ELSE izda := medio + 1

END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7 F

5 4 F

5 6 F

5 T

5

83

Ejemplo valor no encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1

ELSE izda := medio + 1 END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

84

Ejemplo valor no encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1

ELSE izda := medio + 1 END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7 F

85

Ejemplo valor no encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1

ELSE izda := medio + 1 END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7 F

5 4 F

86

Ejemplo valor no encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1

ELSE izda := medio + 1 END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7 F

5 4 F

5 6 F

87

Ejemplo valor no encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1

ELSE izda := medio + 1 END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7 F

5 4 F

5 6 F

4 5 F

88

Ejemplo valor no encontradoizda := 1; der := n; encontrado := FALSE;WHILE (NOT encontrado) AND (izda <= der) DO BEGIN

medio := (izda + der) div 2;encontrado := (V[medio] = buscado);IF (NOT encontrado) THEN

IF (V[medio] > buscado) THEN der := medio – 1

ELSE izda := medio + 1 END;IF encontrado THEN pos := medio;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7 F

5 4 F

5 6 F

4 5 F

89

Búsqueda Binaria

Eliminar una condición de la iteración

buscado en izda Incluir la igualdad

V[medio] <= buscado → erróneo V[medio] >= buscado →

correcto

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

90

Búsqueda Binaria errónea

Si V[medio] > buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

91

izda medio der

>

Búsqueda Binaria errónea

Si V[medio] > buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

92

izda medio der

>

Búsqueda Binaria errónea Si V[medio] > buscado

Si V[medio] <= buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

93

izda medio der

>

izda medio der

<=

Búsqueda Binaria errónea Si V[medio] > buscado

Si V[medio] <= buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

94

izda medio der

>

izda medio der

<=

Búsqueda Binaria errónea

CONSTn = ...;

VARbuscado: <tipo>; V: ARRAY [1..n] OF <tipo>;izda, der: 0..(n+1);pos, medio: 1..n;encontrado: BOOLEAN;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

95

Búsqueda Binaria erróneaizda := 1;der := n;WHILE (izda <> der) DO

BEGINmedio := (izda + der) div 2;IF (V[medio] > buscado) THEN

der := medio – 1ELSE

izda := medio END;

encontrado := (V[izda] = buscado);IF encontrado THEN

pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

96

Búsqueda Binaria errónea1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

97

izda medio der

? ? ?

Búsqueda Binaria errónea1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

98

izda medio der

V[medio] > buscado (der := medio – 1)

der medio

izda? ? ?

> >

Búsqueda Binaria errónea1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

99

izda medio der

V[medio] > buscado (der := medio – 1)

der medio

izda

Fin

? ? ?

> >

Búsqueda Binaria errónea1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

100

izda medio der

V[medio] > buscado (der := medio – 1)

medio der

V[medio] <= buscado (izda := medio)

der medio

izda

izda

Fin

? ? ?

> >

<=

Búsqueda Binaria errónea1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

101

izda medio der

V[medio] > buscado (der := medio – 1)

medio der

V[medio] <= buscado (izda := medio)

der medio

izda

izda

Fin

Bucle Infinito

? ? ?

> >

<=

Búsqueda Binaria correcta

Si V[medio] < buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

102

izda medio der

<

Búsqueda Binaria correcta

Si V[medio] < buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

103

izda medio der

<

Búsqueda Binaria correcta Si V[medio] < buscado

Si V[medio] >= buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

104

izda medio der

<

izda medio der

>=

Búsqueda Binaria correcta Si V[medio] < buscado

Si V[medio] >= buscado

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

105

izda medio der

<

izda medio der

>=

Búsqueda Binaria correcta

CONSTn = ...;

VARbuscado: <tipo>; V: ARRAY [1..n] OF <tipo>;izda, der: 0..(n+1);pos, medio: 1..n;encontrado: BOOLEAN;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

106

Búsqueda Binaria correctaizda := 1;der := n;WHILE (izda <> der) DO

BEGINmedio := (izda + der) div 2;IF (V[medio] < buscado) THEN

izda := medio + 1ELSE

der := medio END;

encontrado := (V[izda] = buscado);IF encontrado THEN

pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

107

Ejemplo valor encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

108

Ejemplo valor encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7

109

Ejemplo valor encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7

5 4

110

Ejemplo valor encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7

5 4

6 6

111

Ejemplo valor encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7

5 4

6 6

5 5

112

Ejemplo valor encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7

5 4

6 6

5 5

T

113

Ejemplo valor encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 7

1 7

5 4

6 6

5 5

T

5

114

Ejemplo valor no encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

115

Ejemplo valor no encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7

116

Ejemplo valor no encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7

5 4

117

Ejemplo valor no encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7

5 4

6 6

118

Ejemplo valor no encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7

5 4

6 6

5 5

119

Ejemplo valor no encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7

5 4

6 6

5 5

F

120

Ejemplo valor no encontradoizda := 1; der := n;WHILE (izda <> der) DO BEGIN

medio := (izda + der) div 2;IF (V[medio] < buscado) THEN izda := medio + 1ELSE der := medio

END;encontrado := (V[izda] = buscado);IF encontrado THEN pos := izda;

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

v[1] v[2] v[3] v[4] v[5] v[6] v[7] bus izd der med enc pos

1 2 3 4 7 10 11 6

1 7

5 4

6 6

5 5

F

121

Medida de la Complejidad de un Algoritmo

Eficiencia de un Algoritmo Memoria necesaria Tiempo de ejecución

Tamaño de la entrada Máquina utilizada Código fuente

Número de ejecucionesinstrucciones del algoritmo

Instrucción Operación Elemental Tiempo constante

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

122

Valores del mejor, peor y caso medio

Número de Instrucciones Ejecutadas

Comparaciones en las que interviene el vector

Colocación de los datos Mejor caso

Poca información Valor Medio de los casos

Difícil de calcular Peor caso

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

123

Comparación de las Estrategias de Búsqueda

Número de Comparaciones (C) Vector de N elementos Búsqueda Secuencial

C = N Búsqueda Binaria

C = log2 N

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

124

Búsqueda Secuencial

Peor CasoBuscado es el último elemento

del vector Tantas comparaciones como

elementos tiene el vector C = N

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

125

Búsqueda Binaria

Peor caso. Si N = 2C

Después de C un elemento donde buscar C = log2 N

1. Búsqueda automática de información

2. Búsqueda en un vector

2.1. Recorrido con Tratamiento Selectivo

2.2. Vector Ordenado

2.3. Concepto de Campo Clave

3. Búsqueda Secuencial

4. Búsqueda Secuencial con Centinela

5. Búsqueda Binaria o Dicotómica

6. Medida de la Complejidad de un Algoritmo

6.1. Valores del mejor, peor y caso medio

6.2. Comparación de las estrategias de búsqueda

Número de comparaciones

Tamaño zona de búsqueda

0 N1 N / 22 N / 22

3 N / 23

... ...C N / 2C

126