剑指Offer第三十七题：数字在数组中出现的次数

题目描述
统计一个数字在排序数组中出现的次数。

解答：有序数组用二分法分别求起始和结束节点（看到有一种解法：就是分别找k+0.5和k-0.5这样过程好像简单一点点）

public class Q_37 {

public int GetNumberOfK(int[] array, int k) {
    if(array.length==0){
        return 0;
    }
    int first = getFirst(array, k);
    int last = getLast(array, k);
    if (first != -1 && last != -1) {
        return last - first + 1;
    }
    return 0;
}

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

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

public static void main(String[] args) {
    int[] s = {1, 2, 2, 3, 3, 3, 3, 5, 6};
    System.out.println(new Q_37().GetNumberOfK(s, 3));
}

}