public class Solution {
    public int GetNumberOfK(int [] array , int k) {

        if (array == null || array.length == 0) {
            return 0;
        }

        int leftIndex = searchLeftIndex(array, 0, array.length - 1, k);
        int rightIndex = searchRightIndex(array, 0, array.length - 1, k);

        if (leftIndex == -1 || rightIndex == -1) {
            return 0;
        }

        return rightIndex - leftIndex + 1;
    }

    public int searchLeftIndex (int[] array, int left, int right, int target) {

        while (left <= right) {

            int mid = left + (right - right) / 2;

            if (array[mid] == target) {
                right = mid - 1;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        if (left < array.length && array[left] == target) {
            return left;
        }

        return -1;
    }

    public int searchRightIndex (int[] array, int left, int right, int target) {

        while (left <= right) {

            int mid = left + (right - right) / 2;

            if (array[mid] == target) {
                left = mid + 1;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        if (right >= 0 && array[right] == target) {
            return right;
        }

        return -1;
    }
}