Ricerca binaria

di

L’algoritmo di ricerca binaria

  • si applica alle sequenze ordinate
  • il codice è più lungo e complesso di quello della ricerca sequenziale
  • ma esegue molto meno passi…
  • la chiamata comune è
    posizione=binaria(LISTA, KEY)

Soluzione 1

def binaria(lista, k):
    inf=0
    sup=len(lista)-1
    TROVATO=False
    while(inf <= sup) and (not TROVATO):
        centro=(inf+sup)//2
        if(lista[centro] < k):
            inf=centro+1
        elif(lista[centro] == k):
            TROVATO=True
        else:
            sup=centro-1

    if(TROVATO):
        return centro
    else:
        return -1

Gli indici inf e sup scorrono dai lati opposti della sequenza fino a raggiungere la posizione di k, se è presente.

Soluzione 2

def binaria(lista, k):
    inf=0
    sup=len(lista)-1
    pos=-1
    while(inf <= sup) and (pos == -1):
        centro=(inf+sup)//2
        if(lista[centro] < k):
            inf=centro+1
        elif(lista[centro] == k):
            pos=centro
        else:
            sup=centro-1

    return pos

Senza la variabile TROVATO

Soluzione 3

def binaria(lista, k):
    inf=0
    sup=len(lista)-1
    while(inf <= sup):
        centro=(inf+sup)//2
        if(lista[centro] < k):
            inf=centro+1
        elif(lista[centro] == k):
            return centro
        else:
            sup=centro-1

    return -1

Senza la variabile pos

Versione ricorsiva

def binaria(lista, k, inf, sup):
    if(inf > sup):
        return -1
    else:
        centro=(inf+sup)//2
        if(lista[centro] < k):
            return binaria(lista, k, centro+1, sup) 
        elif(lista[centro] == k):
            return centro
        else:
            return binaria(lista, k, 0, centro-1)

posizione=binaria(LISTA, KEY, 0, len(LISTA)-1)

Osserva

  • il codice è più compatto
  • non ha variabili locali
  • ha 4 parametri
  • è necessario cambiare la chiamata

Complessità degli algoritmi

Vedi la discusssione

  • T(n)=c_1+c_2 \log{n}