[LeetCode] 33. Search in Rotated Sorted Array

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

Array [ 0, 1,  2,  4,  5,  6, 7 ] can generate below rotated arrays:

0　　1　　2　　 4　　5　　6　　7

7　　0　　1　　 2　　4　　5　　6

6　　7　　0　　 1　　2　　4　　5

5　　6　　7　　 0　　1　　2　　4

4　　5　　6　　7　　0　　1　　2

2　　4　　5　　6　　7　　0　　1

1　　2　　4　　5　　6　　7　　0

Base on the sample data,  it shows that when nums[mid] < nums[right],  the right part is sorted.  Otherwise, the left part is sorted. So we may use the "First" and "Last" number of the sorted part to decide search in left of right part.

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