《剑指 Offer》（第 2 版）第 53 题：数字在排序数组中出现的次数

二分法

传送门：数字在排序数组中出现的次数。

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

例如输入排序数组 [1, 2, 3, 3, 3, 3, 4, 5] 和数字 3 ，由于 3 在这个数组中出现了 4 次，因此输出4。

样例：

输入：[1, 2, 3, 3, 3, 3, 4, 5] , 3

输出：4

参考资料：《剑指 Offer》（第 2 版）第 53 题：数字在排序数组中出现的次数。

思路1：写一个二分法，使用二分法找到大于等于 $k$ 的第 $1$ 个数的下标，再使用二分法找到大于等于 $k+1$ 的第 $1$ 个数的下标，二者之差即为所求。特别注意，这里是如何使用二分法的。

Python 代码：

class Solution(object):
    # 返回大于等于 target 的第 1 个数
    def get_left(self, nums, target):
        # [2,3,4,5,5,5,5,5,5,5]
        # [1,1,1,1,1,1,1,1,1,2,3,4,5,5,5,5,5,5,5]
        if nums[0] == target:
            return 0
        l = 1
        r = len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < target:
                l = mid + 1
            else:
                assert nums[mid] >= target
                # 不能排除 mid
                r = mid
        return l
    def getNumberOfK(self, nums, k):
        """
        :type nums: list[int]
        :type k: int
        :rtype: int
        """
        size = len(nums)
        if size == 0:
            return 0
        return self.get_left(nums, k + 1) - self.get_left(nums, k)

严格按照二分法模板的话，代码要这样写：

Python 代码：

class Solution(object):
    def getNumberOfK(self, nums, k):
        """
        :type nums: list[int]
        :type k: int
        :rtype: int
        """
        size = len(nums)
        if size == 0:
            return 0
        # 设置辅助函数，给一个 nums，一个 k，返回大于等于 k 的第一个数的索引
        return self.__helper(nums, k + 1) - self.__helper(nums, k)
    def __helper(self, nums, k):
        """
        返回大于等于 k 的第一个数的索引
        :param nums:
        :param k:
        :return:
        """
        size = len(nums)
        if size == 0:
            return 0
        l = 0
        # 注意：这里一定要写 size
        r = size - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] >= k:
                r = mid
            else:
                assert nums[mid] < k
                # [1,2,3,4,5]
                l = mid + 1
        # 因为 k 有可能不存在，所以不一定符合要求，所以一定要单独判断一下
        if nums[l] != k:
            if nums[size - 1] < k:
                return size
            elif nums[0] > k:
                return 0
        return l

C++ 代码：

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        if (nums.empty()) return 0;
        return helper(nums, k + 1) - helper(nums, k);
    }
    int helper(vector<int>& nums, int k){
        int l = 0, r = nums.size();
        while (l < r){
            int m = l + (r - l) / 2;
            if (nums[m] < k) l = m + 1;
            else r = m;
        }
        return l;
    }
};

思路2：写两个二分法，一个数出现的次数，一个数最右边的索引 - 一个数最左边的索引 + 1。

# # 56、数字在排序数组中出现的次数
# 统计一个数字在排序数组中出现的次数。
#
# 例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3，由于3在这个数组中出现了4次，因此输出4。
class Solution(object):
    def getNumberOfK(self, nums, k):
        """
        :type nums: list[int]
        :type k: int
        :rtype: int
        """
        size = len(nums)
        if size == 0:
            return 0
        # 设置辅助函数，给一个 nums，一个 k，返回大于等于 k 的第一个数的索引
        k_right = self.__get_right_k(nums, k)
        k_left = self.__get_left_k(nums, k)
        if k_right == -1 or k_left == -1:
            return 0
        return k_right - k_left + 1
    def __get_right_k(self, nums, k):
        # 找到最右边的 index ，使得 nums[index] = k
        size = len(nums)
        if size == 0:
            return -1
        l = 0
        r = size - 1
        while l < r:
            mid = l + (r - l + 1) // 2
            if nums[mid] <= k:
                # [1,2,5,5,5,7]
                l = mid
            elif nums[mid] > k:
                r = mid - 1
        if nums[l] != k:
            return -1
        return l
    def __get_left_k(self, nums, k):
        # 找到最左边的 index ，使得 nums[index] = k
        size = len(nums)
        if size == 0:
            return -1
        l = 0
        r = size - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] >= k:
                r = mid
            else:
                assert nums[mid] < k
                l = mid + 1
        if nums[l] != k:
            return -1
        return l
if __name__ == '__main__':
    nums = [2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10]
    k = 5
    solution = Solution()
    # result = solution.get_left(nums, 5, )
    # print(result)
    result = solution.getNumberOfK(nums, k)
    print(result)

（本节完）