public class Solution {
    public int GetNumberOfK(int[] array, int k) {
        int left = findFirstK(array, 0, array.length-1, k);
        int right = findLastK(array, 0, array.length-1, k);
        if(left==-1||right==-1){
            return 0;
        }else{
            return  right-left+1;
        }
    }

    private int findFirstK(int[] array, int left, int right, int k){
        if(left>right){
            return -1;
        }else if(left==right && array[left]==k){
            return left;
        }
        int mid = (left+right)/2;
        if(array[mid]==k) {
            if ((mid > 0 && array[mid - 1] != k) || mid == 0) {
                return mid;
            }
            right = mid - 1;
        }else if(array[mid]<k){
            left = mid+1;
        }else{
            right = mid-1;
        }
        return findFirstK(array, left, right, k);
    }

    private int findLastK(int[] array, int left, int right, int k){
        if(left>right){
            return -1;
        }else if(left==right && array[left]==k){
            return left;
        }
        int mid = (left+right)/2;
        if(array[mid]==k) {
            if ((mid < array.length-1 && array[mid + 1] != k) || mid == array.length-1) {
                return mid;
            }
            left = mid + 1;
        }else if(array[mid]<k){
            left = mid+1;
        }else{
            right = mid-1;
        }
        return findLastK(array, left, right, k);
    }
}