# 0081. Search in Rotated Sorted Array II
###### tags: `Leetcode` `Medium`
Link: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
## 思路
### Binary Search $O(logN)$ worse case: $O(N)$ $O(1)$
和[0033. Search in Rotated Sorted Array](https://hackmd.io/-HbelXktSrWIauaJrmoYsg)有很多edge case要考虑
思路[参考](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28216/Java-1ms-binary-search-solution-with-comments)
tricky的地方在于```nums[start]```有可能等于```nums[mid]```
如果```nums[start]<nums[mid]```就说明从start到mid都是sorted的，```nums[start]>nums[mid]```则说明从mid到end都是sorted的
### 直接搜寻(C++解法) $O(N)$ $O(1)$
很简单的一道题~只要分情况讨论即可
## Code
### Binary Search $O(logN)$ worse case: $O(N)$ $O(1)$

class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        while(start<end){
            int mid = start+(end-start)/2;
            if(nums[mid]==target) return true;
            if(nums[mid]>nums[start]){
                //start ... mid is sorted
                if(nums[start]<=target && nums[mid]>target){
                    end = mid;
                }
                else{
                    start = mid+1;
                }
            }
            else if(nums[mid]<nums[start]){
                if(nums[mid]<target && target<=nums[end]){
                    start = mid+1;
                }
                else end = mid;
            }
            else start++;
        }
        return nums[start]==target;
    }
}

### 直接搜寻(C++解法) $O(N)$ $O(1)$

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums[0]==target){
            return true;
        }
        else if(nums[0]<target){
            for(int i = 0;i < nums.size();i++){
                if(nums[i] == target){
                    return true;
                }
                if(nums[i] > target){
                    return false;
                }
                if(i < nums.size()-1 && nums[i] > nums[i+1]){
                    return false;
                }
            }
        }
        else{
            for(int i = nums.size()-1;i >= 0;i--){
                if(nums[i] == target){
                    return true;
                }
                if(nums[i] < target){
                    return false;
                }
                if(i > 0 && nums[i] < nums[i-1]){
                    return false;
                }
            }
        }
        return false;
    }
};