1、二分法     空间复杂度O(1),时间复杂度O(logn)    
 思路：二分法找目标值的begin和end，最后begin-end+1，重点是如何找begin和end

1、找begin 
while(left<right){
    mid = (left+right)>>1;  //如果中点值>=目标值，那么证明目标值在(left，min]的左开又闭区间内,那么mid很有可能也是begin  //所以mid也得取到 
      if(array[mid]>=k){
            right = mid;    }  //如果中点值<目标值,那么证明目标值在（min，right）的开区间内，那left=mid+1即可 
       else{
        left = mid+1;  }
}
2、找end
while(left<right){
    mid = (left+right+1)>>1;    //如果中点值<=目标值，那么证明目标值在[mid，right)的左闭又开区间内,那么mid很有可能也是end //所以mid也得取到    
      if(array[mid]<=k)
        {
            right = mid;   
      }  //如果中点值>目标值,那么证明目标值在（left，mid）的开区间内，那right=mid-1即可    
     else{
        right = mid-1; 
      }
}
可以好好理解上面两个模版公式，其中如果出现mid-1，那么在 mid的取值要记得（left+right+1）/2，要加上1，因为要避免向下取整 


public class Solution {
     public int GetNumberOfK(int [] array , int k) {
        if(array.length==0){
            return 0;
        }
        int left = 0;
        int right = array.length-1;
        int mid;
        //找左边界
        while(left<right){
            mid = (left+right)>>1;
            if(array[mid]>=k){
                right = mid;
            }
            else{
                left = mid+1;
            }
        }
         //如果目标值都没有，直接返回0
        if (array[right]!=k){
            return 0;
        }
        int l = right;

        left = 0;
        right = array.length-1;
        //找右边界

        while(left<right){
            mid = (left+right+1)>>1;
            if(array[mid]<=k){
                left = mid;
            }
            else{
                right= mid-1;
            }
        }
        int r = right;
        return r-l+1;
    }
}