在给定的一个已经排好序的数组中,找出指定数字出现的次数;例如数组[1,2,3,3,3,4,5]中3出现的次数为3次。用C语言
时间: 2024-05-03 13:18:37 浏览: 11
可以使用二分查找的思路来解决这个问题。首先用二分查找找到指定数字出现的第一个位置和最后一个位置,然后计算出现次数即可。
下面是代码实现:
```C
#include <stdio.h>
int binarySearch(int arr[], int n, int target, int findFirst) {
int left = 0, right = n - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
ans = mid;
if (findFirst) right = mid - 1;
else left = mid + 1;
}
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return ans;
}
int countOccurrences(int arr[], int n, int target) {
int first = binarySearch(arr, n, target, 1);
int last = binarySearch(arr, n, target, 0);
if (first == -1 || last == -1) return 0;
return last - first + 1;
}
int main() {
int arr[] = {1, 2, 3, 3, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 3;
int count = countOccurrences(arr, n, target);
printf("%d\n", count);
return 0;
}
```
输出结果为:
```
3
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)