二分法计算有序数组中数目字出现的次数

1. 问题描述

　　在给定的一个已经排好序的数组中，找出指定数字出现的次数。例如数组[1,2,3,4,4,4,4,6,8,9]中4出现的次数为4次。

2. 思路与方法

　　此问题可以在二分法的基础上进行改进。假设数组a为递增的数列，需要查找的数字为num，可以分别查找num在数组a中出现的起始位置和最后一次的位置，通过二者的差计算出数字num在数组a中出现的次数。
　　c++代码如下：

#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <set>
#include <vector>
#include <map>

using namespace std;

//查找指定数字在有序数组中出现的次数，isLeft标记最左和最右
int FindCntofNum(int a[],int len, int num, bool isLeft)
{
    int left = 0, right = len -1;

    int pos,mid;

    while(left <= right)//二分查找
    {
        mid = (left + right)/2;

        if( a[mid] < num )
        {
            left = mid +1;
        }
        else if(a[mid] > num)
        {
            right = mid -1;
        }
        else
        {
            pos = mid;

            if(isLeft)//查找最左值
            {
                right = mid -1;
            }
            else//查找最右值
            {
                left = mid +1;
            }
        }
    }
    return pos;//返回最终查找到的位置
}

int main()
{
    int a[10] = { 1,2,3,4,4,4,4,6,8,9};

    int left , right, dst = 4;

    left = FindCntofNum(a,10,4,true);
    right = FindCntofNum(a,10,4,false);

    printf("count of number %d : %d\n",dst,right - left+1);

    return 0;
}