algoritmos de búsquedaausanabria/files/2017iscursos/intro/... · 2017-10-31 · algoritmos de...
TRANSCRIPT
Algoritmos de búsqueda
Introducción a la programación
I semestre, 2017
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
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.
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):
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
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
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
Algoritmos de Búsqueda: secuencial
def busqueda_secuencial(lista, elem):
return busqueda_secuencial_aux(lista, elem, 0, len(lista))
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)
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
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.
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
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
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: -
Búsqueda binaria
def busqueda_binaria(lista, elem):
return busqueda_binaria_aux(lista, elem, 0, len(lista) -1)
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)
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.
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/
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*
Algoritmos de búsqueda
Introducción a la programación
I semestre, 2017
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
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.
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):
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.
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.
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.
Algoritmos de Búsqueda: secuencial
def busqueda_secuencial(lista, elem):
return busqueda_secuencial_aux(lista, elem, 0, len(lista))
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)
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
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.
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
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
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: -
Búsqueda binaria
def busqueda_binaria(lista, elem):
return busqueda_binaria_aux(lista, elem, 0, len(lista) -1)
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)
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.
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/
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*