Introducció

La cerca binària és un algorisme eficient per trobar un element en una llista ordenada. Funciona dividint repetidament la llista en meitats fins a trobar l'element desitjat o determinar que no existeix en la llista.

Conceptes Clau

Llista Ordenada: La cerca binària només funciona en llistes que estan ordenades prèviament.
Divisió i Conquesta: La cerca binària utilitza l'estratègia de "divideix i venceràs" per reduir el problema a subproblemes més petits.

Algorisme

Pseudocodi

funció cerca_binària(llista, element):
    inicialitza esquerra a 0
    inicialitza dreta a longitud de la llista - 1
    
    mentre esquerra ≤ dreta:
        inicialitza mig a (esquerra + dreta) // 2
        
        si llista[mig] == element:
            retorna mig
        si llista[mig] < element:
            esquerra = mig + 1
        si llista[mig] > element:
            dreta = mig - 1
    
    retorna -1  // Element no trobat

Implementació en Python

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  # Element no trobat

Explicació del Codi

Inicialització:
- esquerra i dreta es defineixen per delimitar els extrems de la llista.
Bucle While:
- El bucle continua mentre esquerra sigui menor o igual a dreta.
Càlcul del Punt Mig:
- mig es calcula com la mitjana de esquerra i dreta.
Comparació:
- Si l'element en la posició mig és igual a l'element buscat, es retorna la posició mig.
- Si l'element en mig és menor que l'element buscat, es mou el límit esquerra a mig + 1.
- Si l'element en mig és major que l'element buscat, es mou el límit dreta a mig - 1.
Retorn:
- Si l'element no es troba, es retorna -1.

Complexitat

Complexitat Temporal

Cas Pitjor: O(log n)
Cas Promig: O(log n)
Cas Millor: O(1) (si l'element es troba al mig en la primera iteració)

Complexitat Espacial

Espai Addicional: O(1) (només es necessiten variables addicionals per a esquerra, dreta i mig)

Exercicis Pràctics

Exercici 1

Implementa la funció cerca_binaria en Python i prova-la amb la següent llista i elements:

llista = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
element_a_buscar = 7

Solució

llista = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
element_a_buscar = 7

resultat = cerca_binaria(llista, element_a_buscar)
print(f"Element trobat a la posició: {resultat}")

Exercici 2

Modifica la funció cerca_binaria per retornar una llista amb totes les posicions on es troba l'element buscat (en cas que hi hagi duplicats).

Solució

def cerca_binaria_amb_duplicats(llista, element):
    esquerra, dreta = 0, len(llista) - 1
    posicions = []
    
    while esquerra <= dreta:
        mig = (esquerra + dreta) // 2
        
        if llista[mig] == element:
            posicions.append(mig)
            # Cerca a l'esquerra i a la dreta del mig
            i = mig - 1
            while i >= 0 and llista[i] == element:
                posicions.append(i)
                i -= 1
            i = mig + 1
            while i < len(llista) and llista[i] == element:
                posicions.append(i)
                i += 1
            break
        elif llista[mig] < element:
            esquerra = mig + 1
        else:
            dreta = mig - 1
    
    return posicions if posicions else [-1]

# Prova
llista = [1, 3, 5, 7, 7, 7, 9, 11, 13, 15, 17, 19]
element_a_buscar = 7
resultat = cerca_binaria_amb_duplicats(llista, element_a_buscar)
print(f"Element trobat a les posicions: {resultat}")

Errors Comuns

No Ordenar la Llista: La cerca binària només funciona en llistes ordenades.
Càlcul Incorrecte del Punt Mig: Assegura't de calcular correctament el punt mig per evitar bucles infinits.
No Actualitzar Correctament els Límits: Després de cada comparació, actualitza correctament esquerra o dreta.

Resum

La cerca binària és un algorisme eficient per trobar elements en llistes ordenades, amb una complexitat temporal de O(log n). És essencial entendre el seu funcionament i les seves limitacions per aplicar-lo correctament en la resolució de problemes.

Cerca Binària

Introducció

Conceptes Clau

Algorisme

Pseudocodi

Implementació en Python

Explicació del Codi

Complexitat

Complexitat Temporal

Complexitat Espacial

Exercicis Pràctics

Exercici 1

Solució

Exercici 2

Solució

Errors Comuns

Resum

Curs d'Anàlisi i Disseny d'Algorismes

Mòdul 1: Introducció als Algorismes

Mòdul 2: Anàlisi d'Algorismes

Mòdul 3: Estratègies de Disseny d'Algorismes

Mòdul 4: Algorismes Clàssics

Mòdul 5: Optimització d'Algorismes

Mòdul 6: Pràctiques i Exercicis