# 81. Search in Rotated Sorted Array II

## 1.問題

* 一個sorted array在某個pivot旋轉後, 給予一個數字, 判斷他是否存在

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNcivxVEXEeloBWtcTW%2F-LNck9lXgJIPL4sV8hsQ%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8B%E5%8D%8812.33.08.png?alt=media\&token=aa8e170c-38a0-4243-ab29-e7aa23894512)

## 2.想法&#x20;

* 提問:
* function header, parameter
* test input
* 說明想法&#x20;
  * **binary search**
    * **當mid值大於left值時, 表示左半部已經排序,  先判斷目標是否在左半部, 若是則開始搜尋左半部, 若否則開始搜尋右半部**
    * **當mid值小於left值時, 表示右半部已經排序, 先判斷目標是否在右半部, 若是則開始搜尋右半部, 若否則開始搜尋左半部**
    * **若都不是, 表示mid等於left, 表示重複直, 則回到線性搜尋**
* 測試計算複雜度

## 3.程式碼

```
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int index = searchRotatedSortedArray(nums, 0, nums.size() - 1, target);
        return (index == -1) ? false : true;
    }
private:
    int searchRotatedSortedArray(vector<int>& A, int start, int end, int target) {
        if(start > end) {
            return -1;    
        }
        
        int mid = start + (end-start)/2;
        if(A[mid] == target) {
            return mid;    
        }
        
        if(A[mid] < A[end]) { 
            // right half sorted
            if(target > A[mid] && target <= A[end]) {
                return searchRotatedSortedArray(A, mid+1, end, target);
            } else {
                return searchRotatedSortedArray(A, start, mid-1, target);
            }
        }
        else if (A[mid] > A[end]){  // left half sorted
            if(target>=A[start] && target<A[mid]) {
                return searchRotatedSortedArray(A, start, mid-1, target);
            } else {
                return searchRotatedSortedArray(A, mid+1, end, target);   
            }
        } else {
            return searchRotatedSortedArray(A, start, end-1, target);
        }
    }
};
```
