解法一：顺序查找

顺序查找的思路较为简单：从左至右遍历数组，若找到目标值，返回下标；否则返回-1。

实现的代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param target int整型
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] == target) // 找到直接返回
                return i;
        }
        return -1; // 未找到 返回-1
    }
};

该方法（最坏情况下）需要遍历整个数组，时间复杂度为O(N)；

该方法不需要使用额外空间，空间复杂度为O(1)。

解法二：二分查找

二分查找可以「缩短查找区间」，对于此题，其思路如下：

1. 每次利用mid = (left + right) / 2将整个数组分为左右两个部分，由于数组是旋转而成的，则：必有其中一部分是有序的。在有序的区间内，可以利用二分查找。
2. 假设左半边是有序的，则判断目标值是否在该区域内：
   1. 若在该区域内，则继续利用二分查找进行搜索；
   2. 若不在该区域内，说明目标值在右边区域（无序区域）。重复上述步骤，将该无序区域继续分为两个部分，必有一个是有序的，以此类推。
3. 若右半边是有序的同理。

根据上述思路，得到代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        int n = nums.size(); 
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2; // 中间位置
            if (nums[mid] == target) return mid; // 找到
            if (nums[0] < nums[mid]) { // 若左边是有序的
                if (target >= nums[0] && target <= nums[mid]) { // 若目标值在区间内
                    high = mid - 1; 
                } else { // 目标值不在区间内
                    low = mid + 1; 
                }
            } else { // 右边是有序的
                if (target >= nums[mid] && target <= nums[n - 1]) { // 目标值在区间内
                    low = mid + 1; 
                } else { // 目标值不在区间内
                    high = mid - 1;
                }
            }
        }
        return -1; 
    }
};

该方法采用二分查找算法，时间复杂度为O(logN)；

该方法不需要使用额外空间，空间复杂度为O(1)。