class Solution {
    int binarySearch(int a[], int left, int right, int target)
    {
        if(left > right) return -1;
        int mid = left + right >> 1;
        if(a[mid] == target) return mid;
        else if(a[mid] > target) return binarySearch(a, left, mid - 1, target);
        else return binarySearch(a, mid + 1, right, target);
    }

    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }
}