###### tags: `Leetcode` `medium` `binary search` `python` `Top 100 Liked Questions`

# 33. Search in Rotated Sorted Array

## [題目連結:] https://leetcode.com/problems/search-in-rotated-sorted-array/

## 題目:
There is an integer array nums sorted in ascending order (with **distinct** values).

Prior to being passed to your function, ```nums``` is **possibly rotated** at an unknown pivot index ```k (1 <= k < nums.length)``` such that the resulting array is ```[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]``` (**0-indexed**). For example, ```[0,1,2,4,5,6,7]``` might be rotated at pivot index 3 and become ```[4,5,6,7,0,1,2]```.

Given the array ```nums``` **after** the possible rotation and an integer ```target```, return the index of ```target``` if it is in ```nums```, or ```-1``` if it is not in ```nums```.

You must write an algorithm with ```O(log n)``` runtime complexity.

**Example 1:**

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

**Example 2:**

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

**Example 3:**

Input: nums = [1], target = 0
Output: -1

## 解題想法:
* 兄弟題目:
* [81. Search in Rotated Sorted Array II](/GF7mD5tES_WtMiU9TSGw2w)
* [153. Find Minimum in Rotated Sorted Array](/0j85nVDnRtC-v-kGSSvBgA)
* 題目為: 給一個由小到大排序好的nums
* 但此nums可能是旋轉過後的
* 旋轉: 某位置x，其nums[x:]全移到前面
* ex: [0,1,2,**4**,5,6,7]，**pivot index 3**:
* nums=[**4,5,6,7**,0,1,2]
* 求target是否在nums中
* 要求 O(logN):
* 往binary search思考
* 數組分為: left....mid....right
* 先判斷左(left~mid)右(mid~right)邊哪段是正常的
* 以右半段為例，正常為由小到大
* nums[mid]<=nums[right]
* 再check target是否在此正常的區間內
* 若是: left=mid+1
* 否則: right=mid-1

## Python:

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        #binary search
        left = 0 
        right = len(nums)-1
        while left<=right:
            mid = (left+right)//2
            if target == nums[mid]:
                return mid
            #判斷左半邊是否為有序:ex1234
            #因為正常而言 nums[left]一定是小於等於nums[mid]的 
            #判斷式也可以寫 nums[right]>=nums[mid]
            if nums[left]<=nums[mid]:
                #target在此段落
                if target>=nums[left] and target<nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
            #右半段為有序
            else:
                if target<=nums[right] and target>nums[mid]:
                    left = mid+1
                else:
                    right = mid-1
        return -1

if __name__ == '__main__':
    result = Solution()
    nums = [3,5,1]
    target = 3
    ans = result.search(nums,target)
    print(ans)
    

#Input: nums = [4,5,6,7,0,1,2], target = 0
#Output: 4