class Solution {
    public int search(int[] nums, int target) { 
        return searchAux(nums, target, 0, nums.length-1);
    }
    
    public int searchAux(int[] nums, int target, int right, int left) {
        int middle = right + (left - right)/2;
        
        if(right > left || left >= nums.length || right < 0)
            return -1;
        
        if(target > nums[middle])
            return searchAux(nums, target, middle+1, left);
        if(target < nums[middle])
            return searchAux(nums, target, right, middle-1);
        
        return middle;
    }
}