题解 | #数字在升序数组中出现的次数#

//每次二分查找都是在当前有效数组下进行的，即下标beg到下标end之间
int BinarySearch(int* data, int dataLen, int k, int beg, int end, int mid) {
    if (beg > end) {
        //没找到，直接返回0
        return 0;
    }

    if (data[mid] == k) {
        //找到了一个待查找的值k，并继续分别在左半边数组和右半边数组查找，直到下标beg大于end
        return 1 + BinarySearch(data, dataLen, k, mid + 1, end, mid + 1 + (end - (mid + 1)) / 2) + BinarySearch(data, dataLen, k, beg, mid - 1, beg + (mid - 1 - beg) / 2);
    }
    else if (data[mid] > k) {
        //待查找的值k在当前数组的左半边
        return 0 + BinarySearch(data, dataLen, k, beg, mid - 1, beg + (mid - 1 - beg) / 2);
    }
    else {
        //待查找的值在当前数组的右半边
        return 0 + BinarySearch(data, dataLen, k, mid + 1, end, mid+1 + (end - (mid + 1)) / 2);
    }
}

int GetNumberOfK(int* data, int dataLen, int k) {
    // write code here
    int beg = 0;
    int end = dataLen - 1;
    int mid = beg + (end - beg) / 2;
    int cnt = BinarySearch(data, dataLen, k, beg, end, mid);

    return cnt;
}