> For the complete documentation index, see [llms.txt](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/linear-list/array/search-in-rotated-sorted-array.md).

# Search in Rotated Sorted Array

medium 原题链接：https\://leetcode.com/problems/search-in-rotated-sorted-array/

## Search in Rotated Sorted Array

原题链接：<https://leetcode.com/problems/search-in-rotated-sorted-array/>

### 描述

> You are given an integer array `nums` sorted in ascending order, and an integer `target`.
>
> Suppose that `nums` is rotated at some pivot unknown to you beforehand (i.e., `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`).
>
> *If `target` is found in the array return its index, otherwise, return `-1`.*

### 例子

> Input: nums = \[4,5,6,7,0,1,2], target = 0
>
> Output: 4
>
> Input: nums = \[4,5,6,7,0,1,2], target = 3
>
> Output: -1
>
> Input: nums  = \[1], target = 0
>
> Output: -1

### 约束

> * `1 <= nums.length <= 5000`
> * `-10^4 <= nums[i] <= 10^4`
> * All values of `nums` are **unique**.
> * `nums` is guranteed to be rotated at some pivot.
> * `-10^4 <= target <= 10^4`

### 解法一

无脑遍历数组查找target，用res记录下标并返回。

```cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i=0,res=-1;
        while(i<nums.size()){
            if(nums[i]==target)res=i;
            i++;
        }
        return res;
    }
};
```

分析：T=O(n), S=O(1)

### 解法二

使用二分查找

```cpp
class Solution {
public:
    int search(const vector<int>& nums, int target) { 
        int first = 0, last =nums.size();                                             
        while (first != last) {
            const int mid = first + (last - first) / 2; 
            if (nums[mid] == target)return mid;
            if (nums[first] <= nums[mid]) {
                if(nums[first] <= target && target < nums[mid])
                    last = mid;
                else
                    first = mid + 1;
                } else {
                if(nums[mid] < target && target <= nums[last-1])
                    first = mid + 1;
                else
                    last = mid;
            }
        }
        return -1; 
    }
};
```

分析：T=O（log2 n），S=O（1）

## 总结

从节省时间，降低时间复杂度的角度考虑，优先采用二分查找法。