leetcode-33 Search in Rotated Sorted Array

題意: 在一個rotate array內找出目標值,返回index

解法:做兩次二分查找,第一次找出rotate的點,第二次找出目標值,複雜度O(log n)

我的解法是第一次利用nums[i]>nums[i+1]來判別,但缺點是有時array根本沒被rotate,因此須設定count,若count超過特定值,則中斷,得知array未被rotate,第二次則為一般二分查找

leetcode上有人有更簡潔寫法,第一次查找找出最小值,第二次利用二分查找加移位


我的解法c++ code:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int len=nums.size();
        int left=0;
        int right=len-1;
        int mid=(left+right)/2;
        if(len==0)
            return -1;
        if(len==1)
        {
            if(nums[0]==target)
                return 0;
            else
                return -1;
        }
        int count=0;
        while(nums[mid]<nums[mid+1])
        {
            if(nums[mid]<nums[len-1])
                right=mid-1;
            else
                left=mid+1;
            mid=(left+right)/2;
            count++;
            if(count>100)
                break;
        }
        if(target>nums[0])
        {
            right=mid;
            left=0;
        }
        else
        {
            if(target<nums[0])
            {
                left=mid+1;
                right=len-1;
            }
            else
                return 0;                
        }
        if(count>100)
        {
            left=0;
            right=len-1;
        }
        mid=(left+right)/2;
        count=0;
        while(nums[mid]!=target)
        {
            if(nums[mid]>target)
                right=mid;
            else
                left=mid+1;
            mid=(left+right)/2;
            count++;
            if(count>100)
                return -1;
        }
        return mid;
    }
};