Search This Blog

Tuesday, February 11, 2014

Search an integer in a list with O(logn) complexity if increasingly sorted list rotated n number of times

__author__ = 'nitin'

def rotated_binary_search(alist,item):
    first=0
    last=len(alist)-1
    found=False
    while first<=last:
        mid=(first+last)/2
        if item == alist[mid]:
            return mid
        elif alist[first]<=alist[mid]:
            if item>alist[mid]:
                first=mid+1
            elif item>alist[first]:
                last=mid-1
            else:
                first=mid+1
        elif item            last=mid-1
        elif item<=alist[last]:
            first=mid+1
        else:
            last=mid-1
    return False


alist=[15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]
print rotated_binary_search(alist,20)

No comments:

My Profile

My photo
can be reached at 09916017317