###### tags: `Leetcode` `medium` `binary search` `python`

# 81. Search in Rotated Sorted Array II

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

## 題目:
There is an integer array ```nums``` sorted in non-decreasing order (not necessarily with **distinct** values).

Before being passed to your function, ```nums``` is **rotated** at an unknown pivot index ```k (0 <= 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,4,4,5,6,6,7]``` might be rotated at pivot index 5 and become ```[4,5,6,6,7,0,1,2,4,4]```.

Given the array ```nums``` **after** the rotation and an integer ```target```, return ```true``` if ```target``` is in ```nums```, or ```false``` if it is not in ```nums```.

You must decrease the overall operation steps as much as possible.

**Follow up:** This problem is similar to **[33. Search in Rotated Sorted Array](/Be1uCkocTO-iWb2f-Ne3-Q)**, but nums may contain **duplicates**. Would this affect the runtime complexity? How and why?

**Example 1:**

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

**Example 2:**

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

## 解題想法:
* 兄弟題目:
* [33. Search in Rotated Sorted Array](/Be1uCkocTO-iWb2f-Ne3-Q)
* [153. Find Minimum in Rotated Sorted Array](/0j85nVDnRtC-v-kGSSvBgA)

* 題目為: 給一個由小到大排序好的nums，可能**含有重複數字**
* 但此nums可能是旋轉過後的
* 旋轉: 某位置x，其nums[x:]全移到前面
* ex: [0,1,2,4,4,**4**,5,6,6,7]，**pivot index 5**:
* nums=[**4,5,6,6,7**,0,1,2,4,4]
* 求target是否在nums中

* 使用兩pointer指向頭尾
* head=0
* tail=len(nums)-1
* **每次先判斷nums[head]是否==nums[tail]**
* 若相等表示數字重複，則head+=1
* 再判斷後半段是否為正常升序:
* 即nums[tail]>=nums[mid]:
* 判斷target是否出現在此區間
* 若是: 縮小範圍 head=mid+1
* else: tail=mid-1
* 否則為nums[head]<=nums[mid]:
* 判斷target是否出現在此區間
* 若是: 縮小範圍 tail=mid-1
* else: head=mid+1

## Python:

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        head=0
        tail=len(nums)-1
        while head<=tail:
            #若遇重複的head+1
            while head<tail and nums[head]==nums[tail]:
                head+=1
            mid=(head+tail)//2
            if nums[mid]==target:
                return True
            #判斷哪半段是正常升冪的
            elif nums[tail]>=nums[mid]:
                if nums[mid]<=target<=nums[tail]:
                    head=mid+1
                else:
                    tail=mid-1
            else:
                if nums[mid]>=target>=nums[head]:
                    tail=mid-1
                else:
                    head=mid+1
        return False

result = Solution()
nums = [2,5,6,0,0,1,2]
target = 0
ans = result.search(nums,target)
print(ans)