Search for a Range

• https://leetcode.com/problems/search-for-a-range/

The solution is the same with the problem Count the number of occurrences in a sorted array.

public int[] searchRange(int[] nums, int target) {
    int i = findFirst(nums, 0, nums.length - 1, target);
    if (i == -1) return new int[]{-1, -1};
    int j = findLast(nums, 0, nums.length - 1, target);
    return new int[]{i, j};
}

private int findFirst(int[] array, int left, int right, int target) {
    if (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target && (mid == 0 || target > array[mid - 1])) { // if we find the first occurred element
            return mid;
        } else if (target > array[mid]) {
            return findFirst(array, mid + 1, right, target);
        } else {
            return findFirst(array, left, mid - 1, target);
        }
    } else {
        return -1;
    }
}

private int findLast(int[] array, int left, int right, int target) {
    if (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target && (mid == array.length - 1 || target < array[mid + 1])) { // if we find the first occurred element
            return mid;
        } else if (target < array[mid]) {
            return findLast(array, left, mid - 1, target);
        } else {
            return findLast(array, mid + 1, right, target);
        }
    } else {
        return -1;
    }
}