Binary Search on Rotated Array

rot-bsearch.py

# non-recursive version
def rot_bsearch(xs, val, lo=0, hi=None):
    """
    Binary Search on rotated sorted array.
    >>> rot_bsearch([8,1,2,3,4,5], 5)
    5
    >>> rot_bsearch([], 42)
    -1
    >>> rot_bsearch([1], -1)
    -1
    >>> rot_bsearch([42], 42)
    0
    """
    if hi is None: hi = len(xs)
    while lo < hi:
        mid = lo + (hi - lo) / 2
        if xs[mid] == val:
            return mid
        elif xs[mid] >= xs[lo]:
            # A is sorted
            if xs[lo] <= val < xs[mid]:
                hi = mid
            else:
                lo = mid + 1
        else:
            # B is sorted
            if xs[mid] < val <= xs[hi - 1]:
                lo = mid + 1
            else:
                hi = mid
    return -1

# recursive version
def rot_bsearch_recur(xs, val, lo=0, hi=None):
    """
    Binary Search on rotated sorted array.
    >>> rot_bsearch_recur([8,1,2,3,4,5], 5)
    5
    >>> rot_bsearch_recur([], 42)
    -1
    >>> rot_bsearch_recur([1], -1)
    -1
    >>> rot_bsearch_recur([42], 42)
    0
    """
    if hi is None: hi = len(xs)
    if lo >= hi: return -1
    mid = lo + (hi - lo) / 2
    if xs[mid] == val:
        return mid
    elif xs[mid] >= xs[lo]:
        # A is sorted
        if xs[lo] <= val < xs[mid]:
            return rot_bsearch_recur(xs, val, lo, mid)
        else:
            return rot_bsearch_recur(xs, val, mid + 1, hi)
    else:
        # B is sorted
        if xs[mid] < val <= xs[hi - 1]:
            return rot_bsearch_recur(xs, val, mid + 1, hi)
        else:
            return rot_bsearch_recur(xs, val, lo, mid - 1)

if __name__ == '__main__':
    import doctest
    doctest.testmod()