Take it as a sorted array with binary search in python


  • 3
    L

    This problem can be simply seen as a searching problem in a sorted array. The only difference is to first find the start and end point and extend the index. The extended virtual index will not cause extra space, because you do not need to store them at the end of the original array, but only map them to the original ones. As shown below:

    class Solution:
        # @param A a list of integers
        # @param target an integer
        # @return a boolean
        def search(self, A, target):
            if len(A) == 0:
                return False
            else:
                start = 0
                end = len(A) - 1
                # To find the start point(smallest integer)
                for i in range(len(A)-1):
                    if A[i] > A[i+1]:
                        start = i+1
                        end = i + len(A)    # Extend the index of the list
                while start<=end:
                    mid = start + (end - start)/2
                    cur = A[mid%len(A)] #To get the index in original list
                    if cur == target:
                        return True
                    elif cur > target:
                        end = mid - 1
                    else:
                        start = mid + 1
                
                return False

  • 0
    Y

    Nice idea. One advice, you can always use 'cur = A[mid%len(A)]' to get original index.


  • 0
    L

    Thanks for your suggestion! It surly simplifies the code :)


  • 0
    H

    I thinks the key problem is to find the starting point and the worst case should take O(n) time(like case (a,a,a,a,a,a,a,a,a,a,a,a,b,a,a), b. But if use O(n), just use one loop to find A[i] == target is OK.


  • 0
    L

    yep, I noticed that... So I just closed the question. Thanks!


  • 0
    Z

    I agree with you. When I realized that kind of worst case, I was sure any binary search method is not guaranteed to work.


Log in to reply
 

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