在排序数组中查找元素的第一个和最后一个位置（Medium）
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
Related Topics
数组
二分查找
思路分析
在一个有序的数组中来查找位置，并且题目中要求了logn的时间复杂度，这就等于要求使用二分查找的方式来进行查找。
这里复习一下二分查找，二分查找是一种在有序数组中查找特定元素的高效算法。它的基本思想是将查找的范围分成两部分，每次只考虑其中一半。这个过程不断重复，直到找到目标元素或确定元素不存在。
以下是二分查找的原理和过程：
- 初始化：设置两个指针，分别指向数组的起始位置和结束位置。这两个指针分别代表当前查找范围的下界和上界。
- 计算中间位置：在每一步查找中，先计算中间位置的索引，通常使用下界加上上界减去下界的一半。即 mid = low + (high - low) / 2。
- 比较中间元素：将中间位置的元素和目标元素进行比较：
如果中间元素正好是目标元素，则查找成功，返回该位置的索引。
如果中间元素小于目标元素，则目标元素应该在中间元素的右侧。此时，将下界调整为中间位置的右侧，即 low = mid + 1。
如果中间元素大于目标元素，则目标元素应该在中间元素的左侧。此时，将上界调整为中间位置的左侧，即 high = mid - 1。 - 重复步骤 2 和 3：不断重复上述过程，每次都将查找范围缩小一半。
- 结束查找：当下界大于上界时，表示查找范围内没有目标元素，查找失败。
二分查找的效率很高，它的时间复杂度是 O(log n)，其中 n 是数组的长度。但它的前提条件是数组必须是有序的。
中间的mid使用low + (high - low) / 2进行计算而不是(low+high)/2进行计算，可以有效的避免数值过大而溢出的问题。这点需要注意。
在这道题中要使用两次二分查找，分别对于开始位置以及结束位置进行查找，这就需要对二分查找进行一点修改。用查找开始位置举例，这里由于需要找到最开始的target的位置，所以需要不断的缩小查找范围，找到目标元素也要进行右指针范围的缩小而不是直接结束查找，这里对于右指针的范围进行缩小就可以实现不漏掉左边有可能出现的target最开始出现的位置。直到不满足左指针小于右指针才会查找结束。
代码实现
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[] {
-1, -1};
int first = findFirst(nums, target);
if (first == -1) return new int[] {
-1, -1}; // 如果没找到，直接返回
int last = findLast(nums, target);
return new int[] {
first, last};
}
private int findFirst(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return (nums[left] == target) ? left : -1;
}
private int findLast(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2; // 向上取整
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return (nums[left] == target) ? left : -1;
}
}
//leetcode submit region end(Prohibit modification and deletion)
