Estructuras de Datos I - Búsquedas

Estructura de Datos I

•

UdG

0

Jeremy Esau Valenciano Tadeo

4/7/2023

¡Este material tiene más páginas!

Entonces, ¿te gustó este material?

Ayude a animar a otros estudiantes a mejorar el contenido

¿Te gustó este material? ¡Compartir! 🧡

Estructura de Datos I

24.379 Materiales compartidos

Descarga la aplicación para disfrutar aún más

Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!

Vista previa del material en texto

Estructuras de Datos I
Búsquedas
Búsqueda
La función de búsqueda realiza la localización de un elemento dentro de una lista o arreglo, como resultado devuelve una posición o índice donde se encuentra el elemento, si el elemento no es encontrado devuelve una posición invalida.
				Lineal
				Binaria
Iterativa
Recursiva
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
Posiciones válidas
Posiciones inválidas
Posiciones inválidas
7
8
9
Búsqueda Lineal
43
Elemento
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
0
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
43
Elemento
0
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
0
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
1
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
1
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
1
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
2
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
2
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
2
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
Búsqueda Lineal
3
21
1
43
69
2
93
0
1
2
3
43
Elemento
4
5
6
78
69
1
2
9
7
8
9
ultind
i
Función: BusquedaLineal()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0
			mientras i <= ultind
				¿elemento = array[i]?
					Si: regresar i
				i = i + 1
			fin mientras
		regresar - 1
3
21
1
43
69
2
93
0
1
2
3
78
Elemento
4
5
6
78
69
1
7
8
9
Búsqueda Binaria
78
Elemento
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
Medio
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
Búsqueda Binaria
78
Elemento
0
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
9
J
Medio
Búsqueda Binaria
78
Elemento
0
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
Medio
Búsqueda Binaria
78
Elemento
0
9
ultind
i +
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
5
Medio
Búsqueda Binaria
78
Elemento
0
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
5
Medio
Búsqueda Binaria
78
Elemento
0
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
5
Medio
Búsqueda Binaria
78
Elemento
6
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
5
Medio
Búsqueda Binaria
78
Elemento
6
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
5
Medio
Búsqueda Binaria
78
Elemento
6
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
7
Medio
Búsqueda Binaria
78
Elemento
6
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
7
Medio
Búsqueda Binaria
78
Elemento
6
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento< arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
7
Medio
Búsqueda Binaria
78
Elemento
8
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
9
J
7
Medio
Búsqueda Binaria
78
Elemento
8
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
7
Medio
Búsqueda Binaria
78
Elemento
8
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
8
Medio
Búsqueda Binaria
78
Elemento
8
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
9
J
8
Medio
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
Búsqueda Binaria
78
Elemento
8
9
ultind
i
3
21
1
43
69
2
93
0
1
2
3
4
5
6
78
69
1
7
8
9
Función: BusquedaBinaria()
Recibe: elemento, array, ultind
Regresa: posición
			i = 0, J = ultind
			mientras i <= J
				medio = (i + J) / 2
				¿array[medio] = elemento?
					Si: regresar medio
				¿elemento < arreglo[medio]?
					Si: J = medio - 1
					No: i = medio + 1
			fin mientras
		regresar - 1
9
J
8
Medio
Criterios de evaluación en métodos de búsquedas
Búsqueda Lineal
Búsqueda Binaria
 = n
 = log2 n
Criterios de evaluación en métodos de búsquedas
	Elementos	 = n	 = log2 n
	100	100	7
	1,000	1,000	10
	10,000	10,000	13
	100,000	100,000	17
	1’000,000	1’000,000	20