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

二分的前提：有序（一提到有序，必须立马想到二分！）

int[] array = {1, 2, 3, 3, 3, 5} k=3
=> lowerIndex=2 upperIndex=5
int[] array = {1, 2, 4, 5} k=3
=> lowerIndex=2 upperIndex=2

public class Solution {

    private int upper_bound(int[] array, int val) {
        int l = 0, r = array.length - 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (array[mid] <= val) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private int lower_bound(int[] array, int val) {
        int l = 0, r = array.length - 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (array[mid] < val) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public int GetNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int lowerIndex = lower_bound(array, k);
        int upperIndex = upper_bound(array, k);
        return upperIndex - lowerIndex;
    }
}