Python Solution for this type problem


  • 0
    L

    think of I, middle, j relationship, and you'll get the code:

    class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return an integer
    def search(self, A, target):
        i=0;
        j=len(A)-1;
        while(i<=j):
            middle=int((i+j)/2);
            if(A[middle]==target):
                return middle;
            elif(A[middle]>target):
                if(A[j] > A[middle]):
                    j=middle-1;
                elif(A[j] < A[middle]):
                    if(A[i]>target):
                        i=middle+1;
                    else:
                        j=middle-1;
                else:
                    if(A[i]==A[middle]):
                        i+=1;
                        j-=1;
                    else:
                        j=middle-1;
            else:
                if(A[i] < A[middle]):
                    i=middle+1;
                elif(A[i] > A[middle]):
                    if(A[j] <target):
                        j=middle-1;
                    else:
                        i=middle+1;
                else:
                    if(A[j]==A[middle]):
                        i+=1;
                        j-=1;
                    else:
                        i=middle+1;
        return -1;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.