El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Cerca Binària i Variants

Següent ►
►

Introducció

La cerca binària és un algorisme eficient per trobar un element en una llista ordenada. Funciona dividint repetidament la llista en dues meitats i comparant l'element de la meitat amb l'element que es busca. Aquest algorisme té una complexitat temporal de \(O(\log n)\), la qual cosa el fa molt més ràpid que una cerca lineal \(O(n)\) en llistes grans.

Conceptes Bàsics

Cerca Binària

  1. Llista Ordenada: La cerca binària només funciona en llistes que estan prèviament ordenades.
  2. Divisió i Conquesta: L'algorisme es basa en el principi de dividir la llista en dues parts i conquerir la part que pot contenir l'element buscat.

Pseudocodi

funció cerca_binaria(llista, element):
    inici = 0
    final = longitud(llista) - 1
    
    mentre inici <= final:
        mig = (inici + final) // 2
        
        si llista[mig] == element:
            retorna mig
        si llista[mig] < element:
            inici = mig + 1
        si llista[mig] > element:
            final = mig - 1
    
    retorna -1  # Element no trobat

Implementació en Python

def cerca_binaria(llista, element):
    inici = 0
    final = len(llista) - 1
    
    while inici <= final:
        mig = (inici + final) // 2
        
        if llista[mig] == element:
            return mig
        elif llista[mig] < element:
            inici = mig + 1
        else:
            final = mig - 1
    
    return -1  # Element no trobat

Variants de la Cerca Binària

Cerca Binària Recursiva

La cerca binària també es pot implementar de manera recursiva.

Pseudocodi

funció cerca_binaria_recursiva(llista, element, inici, final):
    si inici > final:
        retorna -1  # Element no trobat
    
    mig = (inici + final) // 2
    
    si llista[mig] == element:
        retorna mig
    si llista[mig] < element:
        retorna cerca_binaria_recursiva(llista, element, mig + 1, final)
    si llista[mig] > element:
        retorna cerca_binaria_recursiva(llista, element, inici, mig - 1)

Implementació en Python

def cerca_binaria_recursiva(llista, element, inici, final):
    if inici > final:
        return -1  # Element no trobat
    
    mig = (inici + final) // 2
    
    if llista[mig] == element:
        return mig
    elif llista[mig] < element:
        return cerca_binaria_recursiva(llista, element, mig + 1, final)
    else:
        return cerca_binaria_recursiva(llista, element, inici, mig - 1)

Cerca Binària en Llistes amb Duplicats

Quan una llista pot contenir elements duplicats, la cerca binària es pot modificar per trobar la primera o l'última aparició d'un element.

Pseudocodi per trobar la primera aparició

funció cerca_binaria_primera_aparicio(llista, element):
    inici = 0
    final = longitud(llista) - 1
    resultat = -1
    
    mentre inici <= final:
        mig = (inici + final) // 2
        
        si llista[mig] == element:
            resultat = mig
            final = mig - 1  # Continua cercant a l'esquerra
        si llista[mig] < element:
            inici = mig + 1
        si llista[mig] > element:
            final = mig - 1
    
    retorna resultat

Implementació en Python

def cerca_binaria_primera_aparicio(llista, element):
    inici = 0
    final = len(llista) - 1
    resultat = -1
    
    while inici <= final:
        mig = (inici + final) // 2
        
        if llista[mig] == element:
            resultat = mig
            final = mig - 1  # Continua cercant a l'esquerra
        elif llista[mig] < element:
            inici = mig + 1
        else:
            final = mig - 1
    
    return resultat

Exercicis Pràctics

Exercici 1: Implementació Bàsica

Implementa una funció de cerca binària iterativa en Python que trobi un element en una llista ordenada.

Solució

def cerca_binaria(llista, element):
    inici = 0
    final = len(llista) - 1
    
    while inici <= final:
        mig = (inici + final) // 2
        
        if llista[mig] == element:
            return mig
        elif llista[mig] < element:
            inici = mig + 1
        else:
            final = mig - 1
    
    return -1  # Element no trobat

Exercici 2: Cerca Binària Recursiva

Implementa una funció de cerca binària recursiva en Python.

Solució

def cerca_binaria_recursiva(llista, element, inici, final):
    if inici > final:
        return -1  # Element no trobat
    
    mig = (inici + final) // 2
    
    if llista[mig] == element:
        return mig
    elif llista[mig] < element:
        return cerca_binaria_recursiva(llista, element, mig + 1, final)
    else:
        return cerca_binaria_recursiva(llista, element, inici, mig - 1)

Exercici 3: Primera Aparició

Implementa una funció de cerca binària que trobi la primera aparició d'un element en una llista ordenada amb elements duplicats.

Solució

def cerca_binaria_primera_aparicio(llista, element):
    inici = 0
    final = len(llista) - 1
    resultat = -1
    
    while inici <= final:
        mig = (inici + final) // 2
        
        if llista[mig] == element:
            resultat = mig
            final = mig - 1  # Continua cercant a l'esquerra
        elif llista[mig] < element:
            inici = mig + 1
        else:
            final = mig - 1
    
    return resultat

Errors Comuns i Consells

  1. Llista No Ordenada: La cerca binària només funciona en llistes ordenades. Assegura't que la llista estigui ordenada abans d'aplicar l'algorisme.
  2. Desbordament d'Enter: En llenguatges de programació amb limitacions d'enter, la suma de inici i final pot causar un desbordament. Utilitza (inici + final) // 2 en lloc de (inici + final) / 2.
  3. Condicions de Bucle: Assegura't que les condicions del bucle while o les condicions de recursió estiguin correctament definides per evitar bucles infinits.

Conclusió

La cerca binària és un algorisme fonamental per a la cerca eficient en llistes ordenades. Les seves variants, com la cerca recursiva i la cerca en llistes amb duplicats, amplien la seva aplicabilitat. Practicar la implementació d'aquests algorismes ajuda a comprendre millor els conceptes de divisió i conquesta i l'eficiència algorítmica.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats