算法-数字在排序数组中出现的次数
算法-数字在排序数组中出现的次数
题目： 统计一个数字在排序数组中出现的次数，比如排序数组为{1,2,3,3,3,4,5}，那么数字3出现的次数就是3。
解题思路： 1.首先，遍历数组肯定就能知道某个数字的个数，此时的时间复杂度O(n)。 2.除此之外，我们注意到，任务本质上是查找问题，而且是排序好的数组，可以尝试用二分查找算法，这样我们可以找到一个3，然后根据这个3向数组的两端遍历，找到所有的3，但是如果3是n个呢？这个算法本质上时间复杂度还是O(n)。 3.最后，我们发现在排序数组中，如果我们知道了第一个3和最后一个3出现的位置，那么其实也就知道了个数，那么我们能否在第一次使用二分查找之后，继续使用二分法，找到两端的3？ 显然可以的，只不过不要稍微修改一些传统二分查找的规则： 如果中间的数字大于3，那么第一个和最后一个3肯定在左半边；
如果中间的数字小于3，那么第一个和最后一个3肯定在右半边；
如果中间的数字等于3，那么需要判断这个3是不是第一个或最后一个3： 如果中间数字左侧相邻的数是3，那么第一个3一定在左半边：
如果中间数字左侧相邻的数不是3，那么第一个3就在中间：
如果中间数字右侧相邻的数是3，那么最后一个3一定在右半边：
如果中间数字右侧相邻的数不是3，那么最后一个3一定就在中间：
所以，我们可以把找第一个和最后一个分成两个问题来考虑，用两个函数分别返回在数组中的位置，那么他们的差值+1就是个数。
个人感觉，二分查找的关键在于用一种规则，让每次查找之后的范围都可以减半，一次来降低时间复杂度，所以改进的二分查找可以很多问题中灵活使用，除了这个，在旋转数组的最小数字问题中也可以用到，甚至在旋转数组的最小数字中，连二分查找的前提条件都变了，不再是一个顺序的数组。
代码实现
int GetNumberOfK(int* data, int length, int k)
{
int number = 0;
if(data != NULL && length > 0)
{
int first = GetFirstK(data, length, k, 0, length - 1);
int last = GetLastK(data, length, k, 0, length - 1);
if(first > -1 && last > -1)
number = last - first + 1;
}
return number;
}
//找第一个k
int GetFirstK(int* data, int length, int k, int start, int end)
{
if(start > end)
return -1;
int middleIndex = (start + end) / 2;
int middleData = data[middleIndex];
if(middleData == k)
{
if((middleIndex > 0 && data[middleIndex - 1] != k)
|| middleIndex == 0)
return middleIndex;
else
end = middleIndex - 1;
}
else if(middleData > k)
end = middleIndex - 1;
else
start = middleIndex + 1;
return GetFirstK(data, length, k, start, end);
}
//找最后一个k
int GetLastK(int* data, int length, int k, int start, int end)
{
if(start > end)
return -1;
int middleIndex = (start + end) / 2;
int middleData = data[middleIndex];
if(middleData == k)
{
if((middleIndex < length - 1 && data[middleIndex + 1] != k)
|| middleIndex == length - 1)
return middleIndex;
else
start = middleIndex + 1;
}
else if(middleData < k)
start = middleIndex + 1;
else
end = middleIndex - 1;
return GetLastK(data, length, k, start, end);
}GetNumberOfK函数没啥好说的，就是在调用，剩下的GetFirstK和GetLastK逻辑是一样的，只要理解一个就好了。
在GetFirstK中，使用了递归的方法，在下一次递归前，一直在调整数组范围，让下一次递归与本次递归相比，范围少了一半，这就是二分。
递归退出的条件就是：
if((middleIndex > 0 && data[middleIndex - 1] != k)
|| middleIndex == 0)