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 , la qual cosa el fa molt més ràpid que una cerca lineal 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
Fem servir cookies per millorar la teva experiència d'ús i oferir continguts adaptats als teus interessos Acceptar Més informació