【剣指offer】数字がソート配列に現れる回数(Java解答)

トピックは、1つの数値kがソート配列に現れる回数を統計することを記述する.
基本構想は並べ替えられた配列であるため,二分法によりkを探すことができる.すべてのkが集まっているので、1つのkを見つけて左と右に検索することができ、kの範囲を得ることができます.
以下に具体的な回答を示します.

public int GetNumberOfK(int [] array , int k) {
    int index = binarySearch(array, k);
    if (index == -1) {
        return 0;
    }
    
    int left = index;
    while (left - 1 >= 0 && array[left-1] == k) {
        left = left - 1;
    }
    
    int right = index;
    while (right + 1 < array.length && array[right+1] == k) {
        right = right + 1;
    }
    
    return right - left + 1;
}

private int binarySearch(int[] array, int k) {
    if (array == null) {
        return -1;
    }
    
    int start = 0;
    int end = array.length - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (array[mid] == k) {
            return mid;
        } else if (array[mid] > k) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    
    return -1;
}