Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar o algoritmo conhecido como busca binária?

+1 voto
105 visitas
perguntada Abr 20, 2016 em Ciência da Computação por danielcajueiro (5,666 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Abr 20, 2016 por danielcajueiro (5,666 pontos)  

Abaixo eu apresento duas implementações usando Python:

def binary_search_rec(theList,key,begin=0,end=-1):
    if(end==-1):
        end=len(theList)-1
    average=(begin+end)//2 # floor div
    if (theList[average]==key):
        return average                 
    else:
        if(begin<end):
            if(theList[average]<key):
                begin=average+1
                return binary_search_rec(theList,key,begin,end)
            else:
                end=average-1
                return binary_search_rec(theList,key,begin,end)
        else:
            return -1


def binary_search(theList,key):
    begin=0    
    end=len(theList)-1

    while(begin<=end):
        average=(begin+end)//2       
        if(theList[average]==key):
            return average
        else:    
            if(theList[average]>key):
                end=average-1
            else:
                begin=average+1
    return -1            



if __name__ == '__main__':

    theList=[1,5,7,9,12,56,78,99,100]

    print binary_search_rec(theList,56)
    print binary_search(theList,56)
...