Not the most concise solution, but a certainly clear one in Python

  • 0
    class Solution:
        # @param A, a list of integers
        # @param target, an integer to be searched
        # @return an integer
        def search(self, A, target):
            def _search(lo, hi):
                if lo >= hi:
                    return -1
                mid = (lo+hi)/2
                if A[mid] == target:
                    return mid
                if A[lo] == A[mid] == A[hi-1]:
                    return max(_search(lo, mid), _search(mid+1, hi))
                elif A[lo] <= A[mid]:
                    if A[lo] <= target < A[mid]:
                        return _search(lo, mid)
                        return _search(mid+1, hi)
                elif A[mid] <= A[hi-1]:
                    if A[mid] < target <= A[hi-1]:
                        return _search(mid+1, hi)
                        return _search(lo, mid)
                    return -1
            return _search(0, len(A)) >= 0

Log in to reply

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