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;
    }

}

4.参考

从有序数组中找出某个数出现的次数