Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de...
Transcript of Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de...
![Page 1: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/1.jpg)
Algoritmos de búsqueda
Introducción a la programación
I semestre, 2017
![Page 2: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/2.jpg)
Algoritmos de Búsqueda
La búsqueda de un elemento determinado en un conjunto de datos es un algoritmo básico para la construcción de una gran cantidad de soluciones:
● ¿cómo encuentro el número de teléfono de un contacto X en mi celular?
● Búsqueda en el web como google.com o duckduckgo.com
![Page 3: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/3.jpg)
Algoritmos de Búsqueda
Algunas características de la forma en la cual están organizados los datos (en la estructura de datos) podarían ser relevantes para determinar el algoritmo a utilizar, a saber: ¿están ordenados?
● Sin orden: se debe realizar una búsqueda secuencial o lineal por toda la lista hasta encontrar el elemento buscado o sino hasta que se llegue al final se podrá asegurar que no existe.
● Ordenados: se pueden utilizar otros algoritmos de búsqueda más eficientes como búsqueda binaria.
![Page 4: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/4.jpg)
Algoritmos de búsqueda: secuencial
Búsqueda secuencial o lineal
Consiste en recorrer de forma secuencial (paso a paso) todos los elementos de la lista hasta encontrar el buscado.
Implementación en python:
● Entradas: una lista y el elemento buscado
● Salidas: posición de elem o una excepción
def busqueda_secuencial(lista, elem):
![Page 5: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/5.jpg)
Algoritmos de búsqueda: secuencial
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
Buscando el elemento 7
![Page 6: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/6.jpg)
Algoritmos de Búsqueda: secuencial
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
Buscando el elemento 7
![Page 7: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/7.jpg)
Algoritmos de Búsqueda: secuencial
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
Buscando el elemento 307
1
8
4
4
11
6
9
8
5
7
![Page 8: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/8.jpg)
Algoritmos de Búsqueda: secuencial
def busqueda_secuencial(lista, elem):
return busqueda_secuencial_aux(lista, elem, 0, len(lista))
![Page 9: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/9.jpg)
Algoritmos de Búsqueda: secuencial
def busqueda_secuencial_aux
(lista, elem, indice, largo):
if indice == largo:
return -1
elif lista[indice] == elem:
return indice
else:
return busqueda_secuencial_aux
(lista, elem, indice+1, largo)
![Page 10: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/10.jpg)
Algoritmos de Búsqueda: binaria
Búsqueda binaria
Consiste en hacer más pequeño el espacio de búsqueda en cada iteración
● De la misma forma que hacemos cuando buscamos una palabra en un diccionarios.
● Lo cual agrega como requisito fundamental para la búsqueda que los elementos estén ordenados
![Page 11: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/11.jpg)
Algoritmos de Búsqueda: binaria
Algoritmo: (asumiendo una lista ordenada ascendentemente)
Se revisa si el elemento buscado es igual al elemento que esté en la mitad del espacio de búsqueda, si es igual se retorna y si no se define un nuevo espacio de búsqueda
El nuevo espacio de búsqueda se define en base a determinar si el elemento buscado es:
● mayor que el elemento en la mitad, entonces ahora se buscará de la misma forma pero solo entre los elementos ubicados entre la mitad y el final de la lista.
● Menor que el elemento en la mitad, entonces ahora se buscará de la misma forma pero solo entre los elementos ubicados entre el inicio de la lista y la mitad.
![Page 12: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/12.jpg)
Algoritmos de Búsqueda: binaria
Búsqueda binaria
Algoritmo: asumiendo una lista ordenada ascendentemente y usando un lenguaje más propio de pseudocódigo...
Conceptos, variables y parámetros:
● Espacio de búsqueda: una lista o sublista en la cual se buscará un elemento.
● Elemento: el valor a buscar en el espacio de búsqueda.
● Inicio: índice del primero elemento del espacio de búsqueda
● Final: largo de la lista
● Mitad: un índice dentro de la lista que se calcula: (inicio + final) // 2
Se revisa si elemento está en la mitad del espacio de búsqueda:
● si es igual se retorna mitad.
● si no se define un nuevo espacio de búsqueda y intenta de nuevo
Nuevo espacio de búsqueda:
Si elemento es mayor que mitad entonces inicio = mitad + 1 y final = final.
Si elemento es menor que mitad entonces inicio = inicio y final = mitad - 1
Implementación en python ?
def busqueda_binaria(lista, elem):
#hacer implementación
![Page 13: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/13.jpg)
Algoritmos de Búsqueda: binaria
1
2
3
4
5
6
7
8
9
10
i: 0, f: 10
mitad: [5]
1
2
3
4
5
6
7
88
9
10
i: 6, f: 10
mitad: [8]
1
2
3
4
5
6
7
8
9
10
i: 6, f: 7
mitad: [6] Buscando el elemento 7
![Page 14: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/14.jpg)
Algoritmos de Búsqueda: binaria
1
2
3
4
5
6
7
8
9
10
i: 0, f: 10
mitad: [5]
1
2
3
4
5
6
7
8
9
10
i: 6, f: 10
mitad: [8]
1
2
3
4
5
6
7
8
9
10
i: 9, f: 10
mitad: [9]
Buscando el elemento 307
1
2
3
4
5
6
7
8
9
10
i: 10, f: 10
mitad: -
![Page 15: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/15.jpg)
Búsqueda binaria
def busqueda_binaria(lista, elem):
return busqueda_binaria_aux(lista, elem, 0, len(lista) -1)
![Page 16: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/16.jpg)
Búsqueda binariadef busqueda_binaria_aux(lista, elem, inicial, final): if final < inicial: return False
mitad = (inicial + final) // 2
if lista[mitad] == elem: return mitad
elif lista[mitad] < elem: return busqueda_binaria_aux(lista, elem, mitad + 1, final)
else: return busqueda_binaria_aux(lista, elem, inicial, mitad – 1)
![Page 17: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/17.jpg)
Algoritmos de Búsqueda: Comparaciones
Búsqueda secuencial
● Problemas: siempre se recorre toda la lista.
● Eficiencia: es directamente proporcional a la cantidad de elementos de la lista. En el peor de los casos se recorre toda.
Búsqueda binaria
● Problemas: la lista debe estar ordenada.
● Eficiencia: Es mucho más rápida que la búsqueda secuencial, en el peor de los casos se recorre el largo de la lista / 2.
![Page 18: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/18.jpg)
Referencias y Lecturas Complementarias
● Material suministrado por el profesor Jeff Schmidt, Instituto Tecnológico de Costa Rica. I semestre 2011.
● J. Helo Guzmán, Introducción a la programación con Scheme, Segunda ed. Cartago: Editorial tecnológica, 2005.
● J. Solano, Introducción a la programación en Python, Primera ed. Cartago: Editorial tecnológica, 2011.
● En general: http://docs.python.org/3/
![Page 19: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/19.jpg)
19
Las presentaciones para el curso IC-1800: "Introducción a la Programación" por Ing. En Computación Alajuela se distribuyen bajo una
Licencia Creative Commons Atribución-Compartir Igual 3.0 Costa Rica.
http://creativecommons.org/licenses/by-sa/3.0/cr/http://creativecommons.org/licenses/by-sa/3.0/cr/ *La licencia de la presentación no cubre las imágenes utilizadas*
![Page 20: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/20.jpg)
Algoritmos de búsqueda
Introducción a la programación
I semestre, 2017
![Page 21: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/21.jpg)
Algoritmos de Búsqueda
La búsqueda de un elemento determinado en un conjunto de datos es un algoritmo básico para la construcción de una gran cantidad de soluciones:
● ¿cómo encuentro el número de teléfono de un contacto X en mi celular?
● Búsqueda en el web como google.com o duckduckgo.com
![Page 22: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/22.jpg)
Algoritmos de Búsqueda
Algunas características de la forma en la cual están organizados los datos (en la estructura de datos) podarían ser relevantes para determinar el algoritmo a utilizar, a saber: ¿están ordenados?
● Sin orden: se debe realizar una búsqueda secuencial o lineal por toda la lista hasta encontrar el elemento buscado o sino hasta que se llegue al final se podrá asegurar que no existe.
● Ordenados: se pueden utilizar otros algoritmos de búsqueda más eficientes como búsqueda binaria.
![Page 23: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/23.jpg)
Algoritmos de búsqueda: secuencial
Búsqueda secuencial o lineal
Consiste en recorrer de forma secuencial (paso a paso) todos los elementos de la lista hasta encontrar el buscado.
Implementación en python:
● Entradas: una lista y el elemento buscado
● Salidas: posición de elem o una excepción
def busqueda_secuencial(lista, elem):
![Page 24: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/24.jpg)
Algoritmos de búsqueda: secuencial
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
Buscando el elemento 7
Se encuentra en la posición [6] de la lista luego de 7 intentos de búsqueda.
![Page 25: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/25.jpg)
Algoritmos de Búsqueda: secuencial
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
Buscando el elemento 7
Se encuentra en la posición [9] de la lista luego de 10 intentos de búsqueda.
![Page 26: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/26.jpg)
Algoritmos de Búsqueda: secuencial
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
1
8
4
4
11
6
9
8
5
7
Buscando el elemento 307
1
8
4
4
11
6
9
8
5
7
No existe, luego de 10 intentos de búsqueda.
![Page 27: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/27.jpg)
Algoritmos de Búsqueda: secuencial
def busqueda_secuencial(lista, elem):
return busqueda_secuencial_aux(lista, elem, 0, len(lista))
![Page 28: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/28.jpg)
Algoritmos de Búsqueda: secuencial
def busqueda_secuencial_aux
(lista, elem, indice, largo):
if indice == largo:
return -1
elif lista[indice] == elem:
return indice
else:
return busqueda_secuencial_aux
(lista, elem, indice+1, largo)
![Page 29: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/29.jpg)
Algoritmos de Búsqueda: binaria
Búsqueda binaria
Consiste en hacer más pequeño el espacio de búsqueda en cada iteración
● De la misma forma que hacemos cuando buscamos una palabra en un diccionarios.
● Lo cual agrega como requisito fundamental para la búsqueda que los elementos estén ordenados
![Page 30: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/30.jpg)
Algoritmos de Búsqueda: binaria
Algoritmo: (asumiendo una lista ordenada ascendentemente)
Se revisa si el elemento buscado es igual al elemento que esté en la mitad del espacio de búsqueda, si es igual se retorna y si no se define un nuevo espacio de búsqueda
El nuevo espacio de búsqueda se define en base a determinar si el elemento buscado es:
● mayor que el elemento en la mitad, entonces ahora se buscará de la misma forma pero solo entre los elementos ubicados entre la mitad y el final de la lista.
● Menor que el elemento en la mitad, entonces ahora se buscará de la misma forma pero solo entre los elementos ubicados entre el inicio de la lista y la mitad.
![Page 31: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/31.jpg)
Algoritmos de Búsqueda: binaria
Búsqueda binaria
Algoritmo: asumiendo una lista ordenada ascendentemente y usando un lenguaje más propio de pseudocódigo...
Conceptos, variables y parámetros:
● Espacio de búsqueda: una lista o sublista en la cual se buscará un elemento.
● Elemento: el valor a buscar en el espacio de búsqueda.
● Inicio: índice del primero elemento del espacio de búsqueda
● Final: largo de la lista
● Mitad: un índice dentro de la lista que se calcula: (inicio + final) // 2
Se revisa si elemento está en la mitad del espacio de búsqueda:
● si es igual se retorna mitad.
● si no se define un nuevo espacio de búsqueda y intenta de nuevo
Nuevo espacio de búsqueda:
Si elemento es mayor que mitad entonces inicio = mitad + 1 y final = final.
Si elemento es menor que mitad entonces inicio = inicio y final = mitad - 1
Implementación en python ?
def busqueda_binaria(lista, elem):
#hacer implementación
![Page 32: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/32.jpg)
Algoritmos de Búsqueda: binaria
1
2
3
4
5
6
7
8
9
10
i: 0, f: 10
mitad: [5]
1
2
3
4
5
6
7
88
9
10
i: 6, f: 10
mitad: [8]
1
2
3
4
5
6
7
8
9
10
i: 6, f: 7
mitad: [6] Buscando el elemento 7
![Page 33: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/33.jpg)
Algoritmos de Búsqueda: binaria
1
2
3
4
5
6
7
8
9
10
i: 0, f: 10
mitad: [5]
1
2
3
4
5
6
7
8
9
10
i: 6, f: 10
mitad: [8]
1
2
3
4
5
6
7
8
9
10
i: 9, f: 10
mitad: [9]
Buscando el elemento 307
1
2
3
4
5
6
7
8
9
10
i: 10, f: 10
mitad: -
![Page 34: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/34.jpg)
Búsqueda binaria
def busqueda_binaria(lista, elem):
return busqueda_binaria_aux(lista, elem, 0, len(lista) -1)
![Page 35: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/35.jpg)
Búsqueda binariadef busqueda_binaria_aux(lista, elem, inicial, final): if final < inicial: return False
mitad = (inicial + final) // 2
if lista[mitad] == elem: return mitad
elif lista[mitad] < elem: return busqueda_binaria_aux(lista, elem, mitad + 1, final)
else: return busqueda_binaria_aux(lista, elem, inicial, mitad – 1)
![Page 36: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/36.jpg)
Algoritmos de Búsqueda: Comparaciones
Búsqueda secuencial
● Problemas: siempre se recorre toda la lista.
● Eficiencia: es directamente proporcional a la cantidad de elementos de la lista. En el peor de los casos se recorre toda.
Búsqueda binaria
● Problemas: la lista debe estar ordenada.
● Eficiencia: Es mucho más rápida que la búsqueda secuencial, en el peor de los casos se recorre el largo de la lista / 2.
![Page 37: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/37.jpg)
Referencias y Lecturas Complementarias
● Material suministrado por el profesor Jeff Schmidt, Instituto Tecnológico de Costa Rica. I semestre 2011.
● J. Helo Guzmán, Introducción a la programación con Scheme, Segunda ed. Cartago: Editorial tecnológica, 2005.
● J. Solano, Introducción a la programación en Python, Primera ed. Cartago: Editorial tecnológica, 2011.
● En general: http://docs.python.org/3/
![Page 38: Algoritmos de búsquedaausanabria/files/2017IScursos/intro/... · 2017-10-31 · Algoritmos de Búsqueda Algunas características de la forma en la cual están organizados los datos](https://reader030.fdocumento.com/reader030/viewer/2022040303/5e8b9f697475344cc0172fbb/html5/thumbnails/38.jpg)
19
Las presentaciones para el curso IC-1800: "Introducción a la Programación" por Ing. En Computación Alajuela se distribuyen bajo una
Licencia Creative Commons Atribución-Compartir Igual 3.0 Costa Rica.
http://creativecommons.org/licenses/by-sa/3.0/cr/http://creativecommons.org/licenses/by-sa/3.0/cr/ *La licencia de la presentación no cubre las imágenes utilizadas*