33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order 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]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

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

Example 2:

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


比较笨的办法, 既然数组被旋转了,找出在哪里旋转的就好.接着就是普通的二分查找,使用stl自带的binary_search也可以.
但是本题有一个test case是  [1,3] 3 ????  这压根没有旋转啊. 所以需要额外一个判断.

class Solution {
public:
    int findMax(vector<int> &nums)
    {
        int l=0,r=nums.size()-1,m;
        while(l<=r)
        {
            m=(l+r)/2;
            if(nums[l]<nums[m]) l=m;
            else if(nums[l]==nums[m]) break;
            else r=m-1;
        }

        return nums[r]>=nums[l]? r:l;
    }
    
    int bs(vector<int> &nums, int l, int r, int t)
    {
        int m;
        while(l<=r)
        {
            m=(l+r)/2;
            if(nums[m]<t)
                l=m+1;
            else if(t<nums[m])
                r=m-1;
            else
                return m;
        }
        return -1;
    }
    int search(vector<int>& nums, int target) {
        if(nums.empty())return -1;
        if(1==nums.size())return nums[0]==target?0:-1;
        int n=nums.back()>=nums[0]? nums.size()-1:findMax(nums);if(target>=nums[0])
            return bs(nums,0,n,target);
        else
            return bs(nums,n+1,nums.size()-1,target);
    }

};