【剑指Offer】数字在排序数组中出现的次数

题目

统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3, 3, 3, 4, 5}和数字3，由于3在这个数组中出现了4次，因此输出4.

实现

public int GetNumberOfK(int[] array , int k) {
    int count = 0;

    if (array != null || array.length <1) {
        int firstIdx = getFirstK(array, k, 0, array.length - 1);
        int lastIdx = getLastK(array, k, 0, array.length - 1);

        if (firstIdx != -1 && lastIdx != -1)
            count = lastIdx - firstIdx + 1;
    }

    return count;
}

private int getFirstK(int[] array, int k, int start, int end) {
    if (start > end)
        return -1;

    int middle = (start + end) / 2;

    if (array[middle] < k)
        return getFirstK(array, k, middle + 1, end);
    else if (array[middle] > k)
        return getFirstK(array, k, start, middle - 1);
    else {
        if (middle == 0 || (middle > 0 && array[middle - 1] != k))
            return middle;
        else
            return getFirstK(array, k, start, middle - 1);
    }
}

private int getLastK(int[] array, int k, int start, int end) {
    if (start > end)
        return -1;

    int middle = (start + end) / 2;

    if (array[middle] < k)
        return getLastK(array, k, middle + 1, end);
    else if (array[middle] > k)
        return getLastK(array, k, start, middle - 1);
    else {
        if (middle == array.length - 1 || (middle < array.length - 1 && array[middle + 1] != k))
            return middle;
        else
            return getLastK(array, k, middle + 1, end);
    }
}