Question

Como implementar o algoritmo conhecido como busca binária?

Answer 1

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)