常考算法题：特殊的二分查找
题目
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
示例 ：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
思路
可以使用二分查找，二分查找就是在有序的列表中查找目标值。因为数组列表目标值存在多个。我们可以利用二分查找目标值的左边界和右边界，即左值二分查找和右值二分查找。同时需要注意目标值在列表中找不到的情况哈。
完整代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = leftBorder(nums,target);
int right = rightBorder(nums,target);
if(left == -3 | right == -3)
return new int []{-1, -1};
else
return new int[] {left + 1, right - 1};
}
private int leftBorder(int[] nums, int target){
int l=0;
int r = nums.length-1;
int leftBorder = -3;
while(l<=r){
int mid = l+ (r-l)/2;
if(nums[mid]==target){
r = mid - 1;
leftBorder = r;
}else if(nums[mid]<target){
l = mid +1;
}else{
r = mid-1;
}
}
return r;
}
private int rightBorder(int[] nums, int target){
int l=0;
int r = nums.length-1;
int rightBorder = -3;
while(l<=r){
int mid = l+ (r-l)/2;
if(nums[mid]==target){
l = mid+1;
rightBorder = l;
}else if(nums[mid]<target){
l = mid +1;
}else{
r = mid-1;
}
}
return rightBorder;
}
}