題目：
統(tǒng)計(jì)一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。例如輸入排序數(shù)組{1,2,3,3,3,3,4,5}和數(shù)字3昂芜，由于3在這個數(shù)組中出現(xiàn)了4次情妖，因此輸出4
解法
分析：
遍歷一次，時(shí)間復(fù)雜度O(n)逮矛，當(dāng)然是可以解決的。
但題目既然強(qiáng)調(diào)是排序數(shù)組转砖，那么可以考慮二分查找须鼎。
解法一：
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出現(xiàn)的index，兩者相減即得個數(shù)
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);
}
}
