1.题目：
有序数组中目标元素出现的次数，要求时间复杂度为O(logn)。
2.思想
数组前提是有序的，因此主要用到了二分查找的思想，找到目标值后，继续向左或者向右查找第一次出现的位置或者最后一次出现的位置，直到没有再找到目标值，那么最后一次记录的索引值就是我们要找的位置。那为什么不在找到目标值后从中间开始往左右两边遍历计数，这样也可以确定目标值的个数呀。但是如果目标值的个数很多，这样岂不是就转换成顺序查找了吗，复杂度为O(n)，因此失去了二分查找的意义。
3.代码
public class 有序数组中某元素的个数logN {
public static void main(String[] args) {
int[]arr={1,1,3,4,5,5,5,6,7};
int target=3;
int left=find(arr,target,0);
int right=find(arr,target,1);
if(left==-1){
System.out.println(0);
}else{
System.out.println(right-left+1);
}
}
public static int find(int[]arr,int target,int flag){
if(arr.length==0)return -1;
int left=0;
int right=arr.length-1;
int last=-1;
while(left<=right){
int mid=(left+right)/2;
if(arr[mid]>target){
right=mid-1;
}else if(arr[mid]<target){
left=mid+1;
}else {
last=mid;
if(flag==0){//找第一个值等于target的索引
right=mid-1;//在左边继续查找
}else if(flag==1){//找最后一个值等于target的索引
left=mid+1;//在右边继续查找
}
}
}
return last;
}
}
