Treating A as Circular Array [Python]


#1
   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
        else:
            return pos(m)
        if prev_m==m:
            if A[pos(m+1)]==B:
                return pos(m+1)
            break
        prev_m = m

    return -1

#2

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.