###### tags: `LeetCode` `Binary Search` `Medium`
# LeetCode #81 [Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)
### (Medium)

已知存在一個按非降序排列的整數數組 nums ，數組中的值不必互不相同。

在傳遞給函數之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉 ，使數組變為 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標 從 0 開始 計數）。例如， [0,1,2,4,4,4,5,6,6,7] 在下標 5 處經旋轉後可能變為 [4,5,6,6,7,0,1,2,4,4] 。

給你 旋轉後 的數組 nums 和一個整數 target ，請你編寫一個函數來判斷給定的目標值是否存在於數組中。如果 nums 中存在這個目標值 target ，則返回 true ，否則返回 false 。

---

使用 if((nums[l] == nums[m]) && (nums[r] == nums[m])) {++l; --r;} 消除重複元素, 除此之外與 [#33](https://hackmd.io/AqU1txS4Q06_R4uQdNC4QA) 相同

---

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l=0, r=nums.size()-1;
        while(l<=r){
            int m = (l+r)>>1;
            if(nums[m]==target)return 1;
            if((nums[l] == nums[m]) && (nums[r] == nums[m])) {++l; --r;}
            else if(nums[l]<=nums[m]){
                if(target>=nums[l]&&target<nums[m])r=m-1;
                else l=m+1;
            }
            else{
                if(target>nums[m]&&target<=nums[r])l=m+1;
                else r=m-1;
            }
        }
        return 0;
    }
};