题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。

示例

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

代码

public int[] searchRange(int[] nums, int target) {
    // 通过二分查找找到左边界
    int left = leftBound(nums, target);
    // 通过二分查找找到右边界
    int right = rightBound(nums, target);
    return new int[]{left, right};
}

int leftBound(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            // 关键步骤
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else if (nums[middle] > target) {
            right = middle - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

int rightBound(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            // 关键步骤
            left = middle + 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else if (nums[middle] > target) {
            right = middle - 1;
        }
    }
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}