Untitled

 avatar
unknown
plain_text
a year ago
1.2 kB
4
Indexable
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(nums[0] < nums[n-1])
        {
            return findTarget(nums, n-1, 0, target);
        }
        
        if(target == nums[0]) return 0;

        int low =0, high = n-1, mid;
        while(low< high){
            mid = low + (high-low)/2;
            if(nums[mid]>=nums[0])
            {
                low = mid+1;
            }
            else
            {
                high = mid;
            }
        }

        if(target > nums[0])
        {
            return findTarget(nums, low-1,0 , target);
        }
        else
        {
            return findTarget(nums,n-1,low,target);
        }
    }

    int findTarget(vector<int>& nums, int high, int low, int target)
    {
        int mid;
        while(low<high)
        {
            mid = low + (high-low)/2;

            if(nums[mid] == target) return mid;
            if(nums[mid]>= target)
            {
                high = mid;
            }
            else
            {
                low = mid+1;
            }
        }
        if(nums[low] == target) return low;
        return -1;
    }
};
Editor is loading...
Leave a Comment