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记录下标并返回。

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)

解法二

使用二分查找

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）

总结

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