Python clean solution with explanation

  • 0

    For this problem, in every iteration of binary search, we need to make sure next pivot falls into the correct segment.

    Given we have mid as pivot index, the status of array falls into either of two cases:
    A. nums[left:mid] is consistently increasing
    B. nums[mid:right] is consistently increasing

    (if both are true, array is not rotated at all, we can treat it as case A )

    For case A, target can only be in the right side of the pivot in following two cases:

    1. Every number in nums[left:mid] is bigger than target (we check if nums[left] is bigger than target)
    2. Every number in nums[left:mid] is smaller than target (we check if nums[mid] is smaller than target)

    else: target MUST be in the left side of the pivot, we go ahead and search left

    For case B, we use the same logic.

    class Solution(object):
        def search(self, nums, target):
            left, right = 0, len(nums)-1
            while right >= left:
                mid = (left+right)/2
                if nums[mid] == target:
                    return mid
                #  if nums[left:mid] is increasing
                if nums[mid] >= nums[left]:
                    if nums[left] > target or nums[mid] <= target:
                        left = mid + 1
                        right = mid - 1
                #  if nums[mid:right] is increasing
                    if nums[right] < target or nums[mid] >= target:
                        right = mid - 1
                        left = mid + 1
            return -1

Log in to reply

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