34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
分析
非递减顺序的意思是升序但是可能存在重复元素，
思路是用一个二分法找结果范围的左边界，再写一个二分法找结果范围的右边界，重点是如何通过二分法查找结果范围的单个边界，
其实方式很简单，以查找结果范围的右边界为例，还是通过二分法来查找，获取区间的中间元素的时候，如果中间元素大于目标值，就更新右区间，如果中间元素小于等于目标值都更新左区间，同时如果 nums[mid]==target，则更新结果范围的右边界，这样的话，扫描完所有的元素之后，我们得到的结果范围的右边界就是索引最大的。
有的时候我们会想使用 left 或者 right 来存储结果范围的左边界或者右边界的值，这个不建议这样做，因为 left 和 right 是循环变量。我们尽量让变量的作用单一。
这里跟经典的二分查找的区别是，经典的二分法写法是遇到目标值就跳出循环，但是这里是查找右边界，因此 nums[mid]==target 依然更新左区间，继续收缩区间
有的时候会想会不会跳过了最终边界，答案是不会，
例如 5 5 5 8 10 12 14 15，目标是是 5
- 当前区间是
[0,7]，nums[3]=8，中间索引的值大于目标值，更新右区间为3-1=2 - 当前区间是
[0,2]，nums[1]=5，中间索引的值小于等于目标值，更新左区间为1+1=2，同时因为nums[1]==5更新结果范围的右边界为 1 - 当前区间是
[2,2]，nums[2]=5，中间索引的值小于等于目标值，更新左区间为2+1=3，同时因为nums[1]==5更新结果范围的右边界为 2
left 为 3，right 为 2，跳出循环，结果范围的右边界为 2
究其原因，主要因为数列是有序的，而且在每一次循环中，我们都在不断更新区间的左右区间，因此，只要我们对左右区间的定义不变，更新左右区间时的操作不出问题，那么在最终跳出循环的时候，我们就能按照我们设定好的方式，遍历完序列中所有的值，二分法的实际效果就是，即使只挑选几个值（每次区间的 mid 值），也能保证不遗漏。二分查找的本质，就是有序数列的一种快速遍历方式。
左边界同理。
常规的二分法有三个变量，查询区间
[start,end]和 区间中间索引值 mid，但是查找边界的二分法有第四个变量，边界 border。 而且常规的二分法以 mid 为最终值，但是查找边界的时候，border 值才是最终返回的值，二分法只是为了快速遍历。为什么二分法能快速遍历，因为数组有序。
通过这个题，我们对二分法的的使用应该有一个更深层次的理解，二分法本质上是一种从有序数组两侧快速往中间逼近的方法，可以有效加快逼近的速度，而且不会遗漏元素。
而且这个题也让我们明白，只要是有序数组，不管有没有重复元素，都可以用二分法
因为本题使用了两次二分查找，所以算法复杂度应该是
解题
public int[] searchRange(int[] nums, int target) {
int leftBorder = binarySearchFromLeft(nums,target);
int rightBorder = binarySearchFromRight(nums,target);
return new int[]{leftBorder,rightBorder};
}
public int binarySearchFromRight(int[] nums,int target){
int start=0, end = nums.length-1;
int rightBorder = -1;
while(start<=end){
int mid = start+(end-start)/2;
if (nums[mid]>target){
// 从右侧确定右边界
end = mid-1;
} else {
start = mid+1;
if(nums[mid]==target){
rightBorder = mid;
}
}
}
return rightBorder;
}
public int binarySearchFromLeft(int[] nums,int target){
int start=0, end = nums.length-1;
int leftBorder = -1;
while(start<=end){
int mid = start+(end-start)/2;
if (nums[mid]<target){
// 从左侧确定左边界
start = mid+1;
} else {
end = mid-1;
if(nums[mid]==target){
leftBorder = mid;
}
}
}
return leftBorder;
}