def binsearch(arr, val, start, end):
if start == end and arr[start] <> val:
return -1
index = (end+start)/2
if val == arr[index]:
return index
elif val < arr[index]:
return binsearch(arr, val, start , index)
elif val > arr[index]:
return binsearch(arr, val, index , end)
arr = range(1,8)
print arr
print binsearch ( arr , 3, 0, len(arr) )
print binsearch ( arr , 7, 0, len(arr) )
Additionnal question:
The array was rotated. How would search in it?
Answer, find the index of max value, iMax and in the previous function, replace
index = (end+start)/2by
index = (iMax + (end+start)/2) % len(arr)
Aucun commentaire:
Enregistrer un commentaire