Python Binary Search


  • 0

    Before running this solution, make sure nums[-1] != nums[0]

    class Solution(object):
        def search(self, nums, target):
            left, right = 0, len(nums) - 1
            if nums[0] == target:
                return True
            while left < right and nums[left] == nums[0]:
                left += 1
            while left < right and nums[right] == nums[0]:
                right -= 1
            while left <= right:
                mid = (left + right) >> 1
                if nums[mid] == target:
                    return True
                if target >= nums[0]:
                    if nums[mid] < target and nums[mid] >= nums[0]:
                        left = mid + 1
                    else:
                        right = mid - 1
                else:
                    if nums[mid] > target and nums[mid] <= nums[-1]:
                        right = mid - 1
                    else:
                        left = mid + 1
            return False
    

Log in to reply
 

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