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)