int bs(int* nums,int left,int right,int target){
    if(left>right) return -1;
    int mid=(left+right)/2;
    if(nums[mid] > target){
        return bs(nums,left,mid-1,target);
    }
    else if(nums[mid] < target){
        return bs(nums,mid+1,right,target);
    }
    else{
        return mid;
    }
}
int search(int* nums, int numsSize, int target){
    return bs(nums,0,numsSize-1,target);
}