剑指Offer35 数组数数（二分查找变形）

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

题目很简单，可以直接遍历一遍完成。但是这样有序的条件运用的就不是很好。有序数组 数字出现的次数 = 最后一个数字下标 - 开始数字的下标。意味着，我们只需要找到开始下标和结束下标就行了。
有序数组寻找一个数最好的方法就是二分查找。那么问题就简单了，使用两次有序查找搞定。

    public int GetNumberOfK(int[] array, int k) {
        // 这里的 +- 0.5 是精华所在
        return indexOf(array, k + 0.5) - indexOf(array, k - 0.5);
    }

    public int indexOf(int[] array, double k) {
        int begin = 0;
        int end = array.length - 1;
        int mid = (begin + end) / 2; //

        while (begin <= end) { 
            // 这里不要使用 < ，当begin = end 的时候，
            //begin不一定是需要的。{1,1,1,1,2} 统计1的数量，会漏掉一个1
            if (array[mid] > k) {
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
            mid = (begin + end) / 2;
        }
        return begin;
    }

---

最后，你也可以向下面这哥们放荡不羁

image.png