LC 0081 [M] Search in Rotated Sorted Array II - ALawliet/algorithms GitHub Wiki

"search in _ sorted array" => binary search for O(logn) beats O(n)

if l <= m, check for target between l and m

else, check for target between m and r

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        # If the length of the given array list is 1, then check the first element and return accordingly
        if len(nums) == 1:
            return nums[0] == target

        l = 0
        r = len(nums) - 1

        while l <= r:
            # shifting to remove duplicate elements
            while l < r and nums[l] == nums[l+1]:
                l += 1
            while l < r and nums[r] == nums[r-1]:
                r -= 1
                
            m = (l + r) // 2

            if nums[m] == target:
                return True
            elif nums[l] <= nums[m]:
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            elif nums[l] > nums[m]:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1

        return False

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        # If the length of the given array list is 1, then check the first element and return accordingly
        if len(nums) == 1:
            return nums[0] == target

        l = 0
        r = len(nums) - 1

        while l <= r:
            # shifting to remove duplicate elements
            while l < r and nums[l] == nums[l+1]:
                l += 1
            while l < r and nums[r] == nums[r-1]:
                r -= 1
                
            m = (l + r) // 2

            if nums[m] == target:
                return True
            elif nums[l] <= nums[m]:
                if nums[l] <= target <= nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            elif nums[l] > nums[m]:
                if nums[m] <= target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1

        return False