数字在排序数组中出现的次数

题目的主要信息：

• 给定一个长度为n的非降序数组和一个数字k，求k在数组中出现的次数

举一反三：

学习完本题的思路你可以解决如下题目：

JZ11. 旋转数组的最小数字

方法：二分法（推荐使用）

知识点：分治

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

思路：

因为data是一个非降序数组，它是有序的，这种时候我们可能会想到用二分查找。但是一个数组可能有多个k，而且我们要查找的并非常规二分法中k出现的位置，而是k出现的左界和k出现的右界。要是能刚好找到恰好小于k的数字位置和恰好大于k的数字的位置就好了。

再有因为数组中全是整数，因此我们可以考虑，用二分查找找到$k+0.5k+0.5$应该出现的位置和$k-0.5k-0.5$应该出现的位置，二者相减就是k出现的次数。

return bisearch(array, k + 0.5) - bisearch(array, k - 0.5);

具体做法：

• step 1：写一个二分查找的函数在数组中找到某个元素出现的位置。每次检查区间中点值，根据与中点的大小比较，确定下一次的区间。
• step 2：分别使用二分查找，找到k+0.5和k-0.5应该出现的位置，中间的部分就全是k，相减计算次数就可以了。

图示：

Java实现代码：

public class Solution {
    //二分查找
    private int bisearch(int[] data, double k){ 
        int left = 0;
        int right = data.length - 1;
        //二分左右界
        while(left <= right){ 
            int mid = (left + right) / 2;
            if(data[mid] < k)
                left = mid + 1;
            else if(data[mid] > k)
                right = mid - 1;
        }
        return left;
    }
    public int GetNumberOfK(int [] array , int k) {
        //分别查找k+0.5和k-0.5应该出现的位置，中间的部分就全是k
        return bisearch(array, k + 0.5) - bisearch(array, k - 0.5);
    }
}

C++实现代码：

class Solution {
public:
    //二分查找
    int bisearch(vector<int>& data, float k){ 
        int left = 0;
        int right = data.size() - 1;
        //二分左右界
        while(left <= right){ 
            int mid = (left + right) / 2;
            if(data[mid] < k)
                left = mid + 1;
            else if(data[mid] > k)
                right = mid - 1;
        }
        return left;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        //分别查找k+0.5和k-0.5应该出现的位置，中间的部分就全是k
        return bisearch(data, k + 0.5) - bisearch(data, k - 0.5);
    }
};

Python实现代码：

class Solution:
    #二分查找
    def bisearch(self, data: List[int], k: float) -> int:
        left = 0
        right = len(data) - 1
        #二分左右界
        while left <= right: 
            mid = (left + right) // 2
            if data[mid] < k:
                left = mid + 1
            elif data[mid] > k:
                right = mid - 1
        return left
    
    def GetNumberOfK(self , data: List[int], k: int) -> int:
        #分别查找k+0.5和k-0.5应该出现的位置，中间的部分就全是k
        return self.bisearch(data, k + 0.5) - self.bisearch(data, k - 0.5)

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，其中$nn$为数组长度，两次二分查找，二分查找复杂度为$O(lo{g}_{2}n)O(log\_2n)$
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间