algoritmos de búsqueda
DESCRIPTION
Algoritmos de Búsqueda. TEMA XIII: Algoritmos de Búsqueda y Ordenación Programación I. 4. 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 - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/1.jpg)
Algoritmos de Búsqueda
TEMA XIII: Algoritmos de Búsqueda y Ordenación
Programación I
![Page 2: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/2.jpg)
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
![Page 3: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/3.jpg)
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
![Page 4: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/4.jpg)
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
![Page 5: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/5.jpg)
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
![Page 6: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/6.jpg)
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
![Page 7: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/7.jpg)
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
![Page 8: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/8.jpg)
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
![Page 9: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/9.jpg)
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
![Page 10: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/10.jpg)
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
![Page 11: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/11.jpg)
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
![Page 12: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/12.jpg)
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
![Page 13: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/13.jpg)
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
![Page 14: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/14.jpg)
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
![Page 15: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/15.jpg)
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
![Page 16: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/16.jpg)
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
![Page 17: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/17.jpg)
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
![Page 18: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/18.jpg)
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
![Page 19: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/19.jpg)
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
![Page 20: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/20.jpg)
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
![Page 21: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/21.jpg)
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
![Page 22: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/22.jpg)
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
![Page 23: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/23.jpg)
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
![Page 24: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/24.jpg)
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
![Page 25: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/25.jpg)
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
![Page 26: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/26.jpg)
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
![Page 27: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/27.jpg)
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
![Page 28: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/28.jpg)
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
![Page 29: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/29.jpg)
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
![Page 30: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/30.jpg)
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
![Page 31: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/31.jpg)
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
![Page 32: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/32.jpg)
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
![Page 33: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/33.jpg)
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
![Page 34: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/34.jpg)
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
![Page 35: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/35.jpg)
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
![Page 36: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/36.jpg)
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
![Page 37: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/37.jpg)
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
![Page 38: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/38.jpg)
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
![Page 39: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/39.jpg)
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
![Page 40: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/40.jpg)
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
![Page 41: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/41.jpg)
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
![Page 42: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/42.jpg)
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
![Page 43: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/43.jpg)
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
![Page 44: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/44.jpg)
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
![Page 45: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/45.jpg)
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
![Page 46: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/46.jpg)
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
![Page 47: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/47.jpg)
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
![Page 48: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/48.jpg)
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
![Page 49: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/49.jpg)
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
![Page 50: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/50.jpg)
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
![Page 51: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/51.jpg)
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
![Page 52: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/52.jpg)
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
![Page 53: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/53.jpg)
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
![Page 54: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/54.jpg)
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
![Page 55: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/55.jpg)
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
![Page 56: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/56.jpg)
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
![Page 57: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/57.jpg)
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
![Page 58: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/58.jpg)
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
![Page 59: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/59.jpg)
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
![Page 60: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/60.jpg)
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
![Page 61: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/61.jpg)
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
![Page 62: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/62.jpg)
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
![Page 63: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/63.jpg)
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
![Page 64: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/64.jpg)
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
![Page 65: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/65.jpg)
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
![Page 66: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/66.jpg)
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
![Page 67: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/67.jpg)
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
![Page 68: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/68.jpg)
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
![Page 69: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/69.jpg)
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
=
![Page 70: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/70.jpg)
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
=
>
![Page 71: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/71.jpg)
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
=
>
![Page 72: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/72.jpg)
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
=
>
<
![Page 73: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/73.jpg)
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
=
>
<
![Page 74: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/74.jpg)
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
![Page 75: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/75.jpg)
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
![Page 76: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/76.jpg)
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
![Page 77: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/77.jpg)
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
![Page 78: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/78.jpg)
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
![Page 79: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/79.jpg)
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
![Page 80: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/80.jpg)
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
![Page 81: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/81.jpg)
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
![Page 82: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/82.jpg)
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
![Page 83: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/83.jpg)
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
![Page 84: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/84.jpg)
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
![Page 85: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/85.jpg)
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
![Page 86: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/86.jpg)
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
![Page 87: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/87.jpg)
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
![Page 88: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/88.jpg)
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
![Page 89: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/89.jpg)
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
>
![Page 90: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/90.jpg)
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
>
![Page 91: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/91.jpg)
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
<=
![Page 92: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/92.jpg)
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
<=
![Page 93: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/93.jpg)
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
![Page 94: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/94.jpg)
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
![Page 95: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/95.jpg)
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
? ? ?
![Page 96: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/96.jpg)
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? ? ?
> >
![Page 97: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/97.jpg)
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
? ? ?
> >
![Page 98: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/98.jpg)
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
? ? ?
> >
<=
![Page 99: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/99.jpg)
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
? ? ?
> >
<=
![Page 100: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/100.jpg)
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
<
![Page 101: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/101.jpg)
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
<
![Page 102: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/102.jpg)
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
>=
![Page 103: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/103.jpg)
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
>=
![Page 104: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/104.jpg)
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
![Page 105: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/105.jpg)
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
![Page 106: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/106.jpg)
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
![Page 107: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/107.jpg)
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
![Page 108: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/108.jpg)
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
![Page 109: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/109.jpg)
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
![Page 110: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/110.jpg)
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
![Page 111: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/111.jpg)
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
![Page 112: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/112.jpg)
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
![Page 113: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/113.jpg)
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
![Page 114: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/114.jpg)
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
![Page 115: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/115.jpg)
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
![Page 116: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/116.jpg)
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
![Page 117: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/117.jpg)
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
![Page 118: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/118.jpg)
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
![Page 119: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/119.jpg)
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
![Page 120: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/120.jpg)
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
![Page 121: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/121.jpg)
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
![Page 122: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/122.jpg)
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
![Page 123: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/123.jpg)
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
![Page 124: Algoritmos de Búsqueda](https://reader036.vdocumento.com/reader036/viewer/2022062816/568146b9550346895db3e3b5/html5/thumbnails/124.jpg)
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