题目描述：

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

实现如下：

方法一

//利用count计数，时间复杂度O(n)
class Solution 
{
public:
	int GetNumberOfK(vector<int> data, int k) 
	{
		return count(data.begin(), data.end(), k);
	}
};

方法二

//从头开始遍历，时间复杂度O(n)
class Solution 
{
public:
	int GetNumberOfK(vector<int> data, int k) 
	{
		int count = 0;
		for (int i = 0; i < data.size(); ++i)
		{
			if (data[i] == k)
				++count;
		}
		return count;
	}
};

方法三

//因为是在排序数组中寻找，所以可以利用二分查找算法
//通过查找第一个k值元素的下标和最后一个k值元素的下标，求出个数
//时间复杂度O(logn)
class Solution 
{
public:
	//寻找第一个k值元素的下标
	int FirstKIndex(vector<int>& data, int k, int left, int right)
	{
		if (left > right)//防御性动作
			return -1;
		int middleIndex = (right - left) / 2 + left;//防止值溢出
		int middleValue = data[middleIndex];//获取中位数的值

		if (middleValue == k)//如果中位数与k相等，则将中位数的前一个数与k比较
		{
			//如果中位数的前一个数不等于k或中位数就是下标0元素，此时中位数的下标就是第一个k值元素的下标
			if ((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0)
				return middleIndex;
			else//若相等，就继续寻找
				right = middleIndex - 1;
		}
		else if (middleValue > k)//如果中位数大于k，则说明第一个k值元素在中位数的前面
			right = middleIndex - 1;
		else//如果中位数小于k，则说明第一个k值元素在中位数的后面
			left = middleIndex + 1;

		return FirstKIndex(data, k, left, right);//递归继续寻找
	}
	
	//寻找最后一个k值元素的下标
	int LastKIndex(vector<int>& data, int k, int left, int right)
	{
		if (left > right)//防御性动作
			return -1;
		int middleIndex = (right - left) / 2 + left;
		int middleValue = data[middleIndex];

		if (middleValue == k)//如果中位数与k相等，则将中位数的后一个数与k比较
		{
			//如果中位数的后一个数不等于k或中位数就是数组中的最后一个元素，此时中位数的下标就是最后一个k值元素的下标
			if ((middleIndex < data.size() - 1 && data[middleIndex + 1] != k) || middleIndex == data.size() - 1)
				return middleIndex;
			else//若相等，就继续寻找
				left = middleIndex + 1;
		}
		else if (middleValue > k)//如果中位数大于k，则说明最后一个k值元素在中位数的前面
			right = middleIndex - 1;
		else//如果中位数小于k，则说明最后一个k值元素在中位数的后面
			left = middleIndex + 1;

		return LastKIndex(data, k, left, right);//递归继续寻找
	}

	int GetNumberOfK(vector<int> data, int k)
	{
		int num = 0;
		if (data.empty()) return 0;

		int first = FirstKIndex(data, k, 0, data.size() - 1);//获取第一个k值元素的下标
		int last = LastKIndex(data, k, 0, data.size() - 1);//获取最后一个k值元素的下标

		if (first > -1 && last > -1)
			num = last - first + 1;计算k值元素个数
		return num;
	}
};