# 81 - Search in Rotated Sorted Array II

解法一 - 稍微修改的 binary search

一開始會很直覺想要用 #33 的做法直接套套看，不過如果直接做，會掛在

[1, 3, 1, 1, 1]
3

這種 case，原因是一開始 nums[mid] == nums[start]，所以就無法分辨到底是 start-mid 有序還是 mid-end 有序。

一個很直覺的做法是，我們可以在遇到 nums[mid] == nums[start] 時，就把 start 往後增加。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int start=0, mid, end=nums.size()-1;
        if(end < 0) return false;

        while(start+1 < end) {
            mid = start + (end-start)/2;

            if(nums[mid] == target) return true;

            bool eqFlag = false;
            while(start<nums.size()-1 && nums[start] == nums[mid]) { start++; eqFlag = true;}
            if(eqFlag) mid = start + (end-start)/2;

            if(nums[start] < nums[mid]) {
                if(nums[start] <= target && target <= nums[mid]) end = mid;
                else start = mid;
            }
            else if(nums[start] > nums[mid]){
                if(nums[mid] <= target && target <= nums[end]) start = mid;
                else end = mid;
            }
        }

        if(nums[start] == target) return true;
        else if(nums[end] == target) return true;
        else return false;
    }
};

這樣做的問題在於，如果整個 array 的值都一樣，那就得花 O(n) 的時間一直 start++。不過這也是無法避免的，畢竟如果整個 array 的值都一樣，那就得看過每個 element 確定 target 不會是突然出現的一個 outlier。