Leetcode 81. Search in Rotated Sorted Array II

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

The 'in' operation is still applicable. The ordinary way is binary search, while due to duplicates, when A[low] == A[mid], we cannot decide where the target is. So we just increase low by 1.

# T:O(lgn) S:O(1)
class Solution:
    # @param A a list of integers
    # @param target an integer
    # @return a boolean
    def search(self, A, target):
        low, high = 0, len(A)
        
        while low < high:
            mid = low + (high - low) / 2
            
            if A[mid] == target:
                return True
            
            if A[low] < A[mid]:
                if A[low] <= target and target < A[mid]:
                    high = mid
                else:
                    low = mid + 1
            elif A[low] > A[mid]:
                if A[mid] < target and target <= A[high - 1]:
                    low = mid + 1
                else:
                    high = mid
            else:
                low += 1
                
        return False

Run Time: 64 ms