二分找左右边界
class Solution {
public int search(int[] nums, int target) {
int start=findLeft(nums,target),end=findRight(nums,target);
if(start==-1||end==-1) return 0;
return end-start+1;
}
public int findLeft(int[] nums, int target){
int n=nums.length;
int l=0,r=n-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]<target){
l=mid+1;
}else{
r=mid-1;
}
}
if(l>=n||nums[l]!=target) return -1;
return l;
}
public int findRight(int[] nums, int target){
int n=nums.length;
int l=0,r=n-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]<target){
l=mid+1;
}else{
l=mid+1;
}
}
if(r<0||nums[r]!=target) return -1;
return r;
}
}