题目：
统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4
解法
分析：
遍历一次，时间复杂度O(n)，当然是可以解决的。
但题目既然强调是排序数组，那么可以考虑二分查找。
解法一：
int findCommonCnt(int *arr, int start, int end, int key) {
if (start > end) return 0;
if (start == end) {
if (arr[start] == key) return 1;
return 0;
}
int mid = (start + end)/2;
if (arr[mid] == key) {
return 1 + findCommonCnt(arr, start, mid-1, key) + findCommonCnt(arr, mid+1, end, key);
} else if (arr[mid] > key) {
return findCommonCnt(arr, start, mid-1, key);
} else {
return findCommonCnt(arr, mid+1, end, key);
}
}
解法二：
分别求出第一个key和最后一个key出现的index，两者相减即得个数
int findFirstK(int *arr, int start, int end, int key) {
if (start > end) return -1;
int mid = (start + end)/2;
if (arr[mid] == key) {
if (mid == 0 || arr[mid-1] < key) return mid;
return findFirstK(arr, start, mid-1, key);
} else if (arr[mid] > key) {
return findFirstK(arr, start, mid-1, key);
} else {
return findFirstK(arr, mid+1, end, key);
}
}
