Treating A as Circular Array [Python]

   def search(self, A, B):
    if len(A)==0:
        return -1
    pvt = A.index(min(A))
    l = 0
    h = len(A)-1 #-pvt
    prev_m = 0
    def pos(n):
        return (n+pos.p[0])%pos.p[1]
    pos.p = (pvt, len(A))

    while l<h:
        m = (l+h)//2
        if A[pos(m)]>B:
            h = m
        elif A[pos(m)]<B:
            l = m
            return pos(m)
        if prev_m==m:
            if A[pos(m+1)]==B:
                return pos(m+1)
        prev_m = m

    return -1


The min() operator and index() operator are both O(n). By using these two operations, doing binary search becomes pointless. A.index(B) would be about as fast as the solution you are proposing.