int bs(int *nums,int sz,int target)
{
    int low = 0,up = sz-1,mid;
    while(low <= up)
    {
        mid = (low + up) >> 1;
        if(nums[mid] > target)
            up = mid -1;
        else if(nums[mid] < target)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

int search(int* nums, int numsSize, int target) {
    int low = 0,step = numsSize - 1;
    while(step && nums[step] == nums[0]) step--;
    while(step)
    {
        while(low + step >= numsSize||nums[low] > nums[low + step])
            step >>= 1;
        low += step;
    }
    if(target >= nums[0])
        return bs(nums,low+1,target) > -1;
    return bs(nums+low+1,numsSize - low-1,target) > -1;
}