排序数组中查找元素的起始和结束位置

题目

给定一个按照升序排列的整数数组nums，和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target，返回[-1, -1]。
示例1：

输入：nums=[5, 7, 7, 8, 8, 10], target=8
输出：[3, 4]
解释：target8在数组nums中，并且起始位置为3，结束位置为4

示例2：

输入：nums=[5, 7, 7, 8, 8, 10], target=4
输出：[-1, -1]
解释：target4不存在于nums中

解法：二分查找

public class Main {
    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] result = searchRange(nums, target);
        System.out.println("Start position: " + result[0]);
        System.out.println("End position: " + result[1]);
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int left = binarySearch(nums, target, true);
        if (left == nums.length || nums[left] != target) {
            return result;
        }
        result[0] = left;
        result[1] = binarySearch(nums, target, false) - 1;
        return result;
    }

    private static int binarySearch(int[] nums, int target, boolean leftmost) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (leftmost && nums[mid] == target)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

这里使用了二分查找算法来定位目标值的起始位置和结束位置。首先，我们使用 binarySearch 方法找到目标值的起始位置，然后再次调用 binarySearch 方法找到目标值的结束位置。在 binarySearch 方法中，我们使用了一个额外的布尔值 leftmost 来判断是否查找起始位置。返回的结果是目标值的索引位置。

在 searchRange 方法中，我们首先查找目标值的起始位置 left。如果 left 等于数组的长度或者 nums[left] 不等于目标值，则说明数组中不存在目标值，返回 [-1, -1]。否则，将起始位置 left 存入结果数组的第一个元素。接着，我们使用 binarySearch 方法查找目标值的结束位置，并将其减去1后存入结果数组的第二个元素。最后，返回结果数组。