LeetCode解題之Search in Rotated Sorted Array

原題

把一個嚴格升序的數組進行旋轉，如[0,1,2,3,4,5]旋轉3位成為[3,4,5,0,1,2]。在這樣的數組中找到目標數字。如果存在返回下標，不存在返回-1。

注意點：

例子：

輸入: nums = [4, 5, 6, 7, 0, 1, 2], target = 6
輸出: 2

輸入: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
輸出: -1

解題思路

采用了二分搜索，不過旋轉後的數組要討論的情況增多了。其實旋轉後的數組的大小關系一般如下圖：

     /
    /
   /
  /
             /
            /
           /

先通過中點與左頂點的關系來分類討論中點落在了哪一部分，如果在左半邊，則繼續討論目標數在中點的左邊還是右邊；如果在右半邊，同樣討論目標數的位置。同時需要注意特殊情況只剩下兩個數時，例如[3,1]，這時求出的中點也是3，如果中點不匹配，應考慮1。這種情況不好與上面的情況合並，單獨列出。

AC源碼

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] > nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[mid] < nums[left]:
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                left += 1
        return -1


if __name__ == "__main__":
    assert Solution().search([4, 5, 6, 7, 0, 1, 2], 4) == 0
    assert Solution().search([4, 5, 6, 7, 0, 1, 2], 7) == 3
    assert Solution().search([4, 5, 6, 7, 0, 1, 2], 0) == 4
    assert Solution().search([4, 5, 6, 7, 0, 1, 2], 2) == 6
    assert Solution().search([3, 1], 3) == 0
    assert Solution().search([3, 1], 1) == 1

歡迎查看我的Github來獲得相關源碼。