题目：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
解题思路：
如何查找元素在数组中的开始位置？
只需要在while中，即使nums[i]==target时，也将right = mid - 1。这样循环结束后的left就是第一个大于等于target的位置，如果等于target，则是target在数组中的开始位置；如果不等于target，则说明数组中没有target。（在插入问题中，此时的left则是target的插入位置）。
那么同理，如何查找元素在数组中的结束位置呢？
只需要在while中，即使nums[i]==target时，也将left= mid + 1。这样循环结束时的right就是最后一个小于等于target的位置。
如果没有target的开始位置，说明数组中没有这个元素，自然也就不必再找结束位置了，可以提前返回答案。
class Solution {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
int first = 0, last = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (left < n && nums[left] == target) {
first = left;
} else {
// 不存在target，直接返回
return new int[]{-1, -1};
}
left = 0;
right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 前面已经判断存在target，那么就肯定存在最后一个位置，不用再判断right合法性
last = right;
return new int[]{first, last};
}
}
优化：
其实我们在找结束位置时，可以不用新的二分查找逻辑，我们只需要复用查找开始位置的二分查找逻辑即可，只不过我们查找的不再是target的开始位置，而是target+1的开始位置，我们找到了target+1的开始位置，那么该位置的前一个位置自然就是target的结束位置了。
class Solution {
public int[] searchRange(int[] nums, int target) {
int first = binSearch(nums, target);
if(first == nums.length || nums[first] != target){
return new int[]{-1, -1};
}
int last = binSearch(nums, target + 1) - 1;
return new int[]{first, last};
}
private int binSearch(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 - 1;
}
}
return left;
}
}