/*

题目：

	统计一个数字在排序数组中出现的次数。

*/

/*

思路：

	1、从前往后遍历，时间复杂度O(n)。

	2、二分查找到目标数字target，向前向后遍历，时间复杂度O(n)。

	3、利用二分法，递归找到数字出现的第一个位置和最后一个位置，时间复杂度O(logn)。

*/

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<map>

using namespace std;

int getFirstOfK(vector<int> &A,int start,int end, int target){

    if(start > end) return -1;

    int mid = (start + end) / 2;

    if(A[mid] > target){

        return getFirstOfK(A,start,mid-1,target);

    }else if(A[mid] < target){

        return getFirstOfK(A,mid+1,end,target);

    }else{

        if(mid == 0 || A[mid-1] != target){

            return mid;

        }else{

            return getFirstOfK(A,start,mid-1,target);

        }

    }

}

int getLastOfK(vector<int> &A,int start,int end,int target){

    if(start > end) return -1;

    int mid = (start+end) / 2;

    if(A[mid] > target){

        return getLastOfK(A,start,mid-1,target);

    }else if(A[mid] < target){

        return getLastOfK(A,mid+1,end,target);

    }else{

        if(mid == end || A[mid+1] != target){

            return mid;

        }else{

            return getLastOfK(A,mid+1,end,target);

        }

    }

}

int getNumbersOfK(vector<int> &A, int target){

    int first = getFirstOfK(A,0,A.size()-1,target);

    int last = getLastOfK(A,0,A.size()-1,target);

    if(last != -1 && first != -1){

        return last - first + 1;

    }

    return 0;

}

int main(){

   vector<int> a = {1,1,3,4,4,4,5};

   cout<<getNumbersOfK(a,1);

}