升序数组中求一个key出现的次数

算法思路： 在排好序的数组，相同的数字是排列在一起的，所以只需要找到key的左边界和右边界即可。

找左边界可以看成是找数组中第一个大于等于key的数的位置，找右边界可以看成是找最后一个小于等于key的数。

复杂度分析：时间复杂度是O(log(n))，空间复杂度是O(n)。

 

#include <stdio.h>
/*
 * @brief 在升序数组a中找到第一个大于等于key的数的位置,如果不存在这样的位置，例如
 * 数组a中所有的数字都比key小，则返回的数是n
 * @parma int* a 升序数组
 * @parma int n  数组a的长度
 * @int key 待查找的关键字
 */
int find_left(int* a, int n, int key){
    int l, r, mid; 
    l = 0; 
    r = n-1;
    while(l <= r){
        int mid = (l+r) >> 1; 
        if(a[mid] >= key) r=mid-1; 
        else l=mid+1; 
    }
    return r+1; 
}

/*
 * @brief 在升序数组a中找到最后一个小于等于key的数的位置,如果不存在这样的位置，例如
 * 数组a中所有的数字都比key大，则返回的数是-1
 * @parma int* a 升序数组
 * @parma int n  数组a的长度
 * @int key 待查找的关键字
 */
int find_right(int* a, int n, int key){
    int l, r, mid; 
    l = 0; 
    r = n-1;
    while(l <= r){
        int mid = (l+r)>>1; 
        if(a[mid] <= key) l = mid + 1; 
        else r = mid - 1; 
    }    
    return l-1; 
}
int count(int* a, int n, int key){
    int l = find_left(a, n, key);
    int r = find_right(a, n, key);
    int cnt = r-l+1; 
    return cnt; 
}
int main(){
	//输入和输出重定向
	freopen("in.txt","r", stdin);
	freopen("out.txt", "w", stdout);
	const int N = 4; 
	int a[N] = {2, 4, 4, 5}, key; 
	//use case 1：key比数组中所有的数都要小
	key = 1; 
	printf("%d出现的次数是%d\n", key, count(a, N, key));

	//use case 2：key在数组出现了一次
	key = 2; 
	printf("%d出现的次数是%d\n", key, count(a, N, key));

	//use case 3：key在数组出现了不止一次
	key = 4; 
	printf("%d出现的次数是%d\n", key, count(a, N, key));

	//use case 4：key不在数组中，但大于数组中的最小数，小于数组中的最大数
	key = 3; 
	printf("%d出现的次数是%d\n", key, count(a, N, key));

	//use case 5：key比数组中的最大数还大
	key = 6; 
	printf("%d出现的次数是%d\n", key, count(a, N, key));

    return 0; 
}

 输出结果如下：

1出现的次数是0

2出现的次数是1

4出现的次数是2

3出现的次数是0

6出现的次数是0