# 33. Search in Rotated Sorted Array

## 1.問題&#x20;

* 假設有個依升冪排序的array, 在某個pivot旋轉, 給予一個target, 找出他在array中的位置, 若找不到則回傳-1

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LHNhRAF5RjcMn1WXZ0V%2F-LHNiTKP-0suyA4POsVF%2F2018071405.jpg?alt=media\&token=7279dfab-5023-4416-8ccf-01d60d126581)

## 2.想法&#x20;

* 這題必須使用[Binary search](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/binary-search)來做, 但是rotated list不是sorted list

## 3.程式碼&#x20;

```
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        return searchRotatedSortedArray(nums, 0, n-1, target);
    }
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 {  // 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);   
            }
        }
    }
};
```



