dimanche 30 mai 2010

Binary search and array rotation

The following solution has been implemented and verified:

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)/2
by
    index = (iMax + (end+start)/2) % len(arr)

Aucun commentaire:

Enregistrer un commentaire