剑指offer 面试题38：数字在排序数组中出现的次数

题目：
统计一个数字在排序数组中出现的次数。例如输入排序数组{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);
    }
}