En aquest tema, explorarem els conceptes bàsics dels algoritmes de cerca, que són fonamentals en la programació i la informàtica. Els algoritmes de cerca s'utilitzen per trobar un element específic dins d'una estructura de dades com ara una llista o un array. Aprendrem sobre els dos tipus d'algoritmes de cerca més comuns: la cerca lineal i la cerca binària.
Objectius d'aprenentatge
Al final d'aquest tema, hauràs de ser capaç de:
- Comprendre què és un algoritme de cerca.
- Implementar la cerca lineal.
- Implementar la cerca binària.
- Comparar l'eficiència dels dos tipus de cerca.
- Cerca Lineal
Descripció
La cerca lineal és el mètode més simple de cerca. Consisteix a recórrer la llista o array element per element fins a trobar l'element desitjat o fins a arribar al final de la llista.
Exemple de codi
def cerca_lineal(llista, element):
for i in range(len(llista)):
if llista[i] == element:
return i # Retorna la posició de l'element
return -1 # Retorna -1 si l'element no es troba a la llista
# Exemple d'ús
llista = [4, 2, 7, 1, 3]
element = 7
resultat = cerca_lineal(llista, element)
print(f"L'element {element} es troba a la posició {resultat}")Explicació del codi
- La funció
cerca_linealpren com a paràmetres una llista i l'element que es vol cercar. - Utilitza un bucle
forper recórrer cada element de la llista. - Si l'element actual és igual a l'element que es busca, retorna la posició de l'element.
- Si el bucle acaba sense trobar l'element, retorna -1.
Exercici pràctic
Implementa una funció de cerca lineal que cerqui un número en una llista de nombres i retorni la posició de l'última aparició del número.
def cerca_lineal_ultima_aparicio(llista, element):
# Implementa la funció aquí
pass
# Prova la teva funció
llista = [4, 2, 7, 1, 3, 7, 8]
element = 7
resultat = cerca_lineal_ultima_aparicio(llista, element)
print(f"L'última aparició de l'element {element} es troba a la posició {resultat}")Solució
def cerca_lineal_ultima_aparicio(llista, element):
posicio = -1
for i in range(len(llista)):
if llista[i] == element:
posicio = i
return posicio
# Prova la teva funció
llista = [4, 2, 7, 1, 3, 7, 8]
element = 7
resultat = cerca_lineal_ultima_aparicio(llista, element)
print(f"L'última aparició de l'element {element} es troba a la posició {resultat}")
- Cerca Binària
Descripció
La cerca binària és un mètode de cerca més eficient que la cerca lineal, però requereix que la llista estigui ordenada. Divideix repetidament la llista en dues meitats i compara l'element del mig amb l'element que es busca.
Exemple de codi
def cerca_binaria(llista, element):
esquerra, dreta = 0, len(llista) - 1
while esquerra <= dreta:
mig = (esquerra + dreta) // 2
if llista[mig] == element:
return mig
elif llista[mig] < element:
esquerra = mig + 1
else:
dreta = mig - 1
return -1
# Exemple d'ús
llista = [1, 2, 3, 4, 7, 8]
element = 7
resultat = cerca_binaria(llista, element)
print(f"L'element {element} es troba a la posició {resultat}")Explicació del codi
- La funció
cerca_binariapren com a paràmetres una llista ordenada i l'element que es vol cercar. - Defineix dos índexs,
esquerraidreta, que representen els límits de la part de la llista que s'està considerant. - Utilitza un bucle
whileper continuar dividint la llista fins queesquerrasigui major quedreta. - Calcula l'índex del mig i compara l'element del mig amb l'element que es busca.
- Si l'element del mig és igual a l'element que es busca, retorna la posició.
- Si l'element del mig és menor, ajusta
esquerraper considerar només la meitat dreta de la llista. - Si l'element del mig és major, ajusta
dretaper considerar només la meitat esquerra de la llista. - Si el bucle acaba sense trobar l'element, retorna -1.
Exercici pràctic
Implementa una funció de cerca binària que cerqui un número en una llista ordenada de nombres i retorni la posició de la primera aparició del número.
def cerca_binaria_primera_aparicio(llista, element):
# Implementa la funció aquí
pass
# Prova la teva funció
llista = [1, 2, 3, 4, 7, 7, 8]
element = 7
resultat = cerca_binaria_primera_aparicio(llista, element)
print(f"La primera aparició de l'element {element} es troba a la posició {resultat}")Solució
def cerca_binaria_primera_aparicio(llista, element):
esquerra, dreta = 0, len(llista) - 1
resultat = -1
while esquerra <= dreta:
mig = (esquerra + dreta) // 2
if llista[mig] == element:
resultat = mig
dreta = mig - 1 # Continua cercant a l'esquerra
elif llista[mig] < element:
esquerra = mig + 1
else:
dreta = mig - 1
return resultat
# Prova la teva funció
llista = [1, 2, 3, 4, 7, 7, 8]
element = 7
resultat = cerca_binaria_primera_aparicio(llista, element)
print(f"La primera aparició de l'element {element} es troba a la posició {resultat}")Comparació d'Eficiència
Taula Comparativa
| Algoritme | Complexitat en el pitjor cas | Requisits de la llista |
|---|---|---|
| Cerca Lineal | O(n) | Cap |
| Cerca Binària | O(log n) | Llista ordenada |
Resum
- La cerca lineal és simple i no requereix que la llista estigui ordenada, però pot ser lenta per a llistes grans.
- La cerca binària és molt més eficient per a llistes grans, però requereix que la llista estigui ordenada.
Conclusió
En aquest tema, hem après sobre dos tipus d'algoritmes de cerca: la cerca lineal i la cerca binària. Hem vist com implementar-los i hem comparat la seva eficiència. Ara estàs preparat per aplicar aquests coneixements en situacions reals de programació.
En el següent tema, explorarem els algoritmes d'ordenació, que són essencials per preparar les llistes per a una cerca binària eficient.
Fonaments de la Programació
Mòdul 1: Introducció a la Programació
- Què és la programació?
- Història de la programació
- Llenguatges de programació
- Entorns de desenvolupament