力扣第34题-在排序数组中查找元素的第一个和最后一个位置

题目
题目链接

题解

class Solution {

    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        return recurrence(nums, target, 0, nums.length - 1);
    }

    private int[] recurrence(int[] nums, int target, int left, int right) {
        int[] res = new int[2];
        // 二分查找
        int findIndex = binarySearch(nums, target, left, right);
        res[0] = findIndex;
        res[1] = findIndex;
        if (findIndex != -1 && findIndex != left) {
            // 递归左边的数组
            int[] leftArray = recurrence(nums, target, left, findIndex - 1);
            // 如果左边没有目标值，直接取当前找到的下标给本次方法结果的左边界
            if (leftArray[0] == -1) {
                res[0] = findIndex;
            } else {
                res[0] = leftArray[0];
            }
        }
        if (findIndex != -1 && findIndex != right) {
            // 递归右边的数组
            int[] rightArray = recurrence(nums, target, findIndex + 1, right);
            // 如果右边没有目标值，直接取当前找到的下标给本次方法结果的右边界
            if (rightArray[1] == -1) {
                res[1] = findIndex;
            } else {
                res[1] = rightArray[1];
            }
        }
        return res;
    }

    /**
     * 普通二分查找
     * @param nums 数组
     * @param target 目标
     * @param left 左起点
     * @param right 右起点
     * @return 目标下标，-1为没找到
     */
    private int binarySearch(int[] nums, int target, int left, int right) {
        if (nums == null || nums.length < 1 || left < 0 || right < 0 || left > right || left > nums.length - 1 || right > nums.length - 1) {
            return -1;
        }
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}