c++11 - 递归计算排序数组中某个键出现的次数

Question

我试图递归地解决这个问题http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/ 。到目前为止，我的代码使用了一个带有静态变量的愚蠢的小技巧。虽然这可行，但如果您使用不同的键重复调用该函数，则会失败(因为静态变量仍然会记住以前的设置值)。

int FindCount(const vector< int > &A, int l, int r, int B)
{
    static int count =0;
    // cout<<l<<' '<<r<<endl;
    if(l <= r)
    {
        int mid = (l+r)/2;
        // cout<<mid<<endl;
        if(A[mid] == B)
        {
            count++;
            FindCount(A, l, mid-1, B);
            FindCount(A, mid+1, r, B);
        }
        else if (A[mid] < B)
        {
            FindCount(A, mid+1, r, B);
        }
        else
        {
            FindCount(A, l, mid-1, B);
        }
    }
    return count;
}

我可以弄清楚它应该如何工作，但很难将其转换为代码。应该是这样的，一旦找到特定的键就返回1并继续递归地搜索该键的左侧和右侧。

你能帮我在不使用静态变量的情况下以更清晰的代码递归地完成此操作吗:)

Answer 1

int FindCount(const vector< int > &A, int l, int r, int B)
{
      int count = 0;
      if(l <= r)
      {
          int mid = (l+r)/2;
          if(A[mid] == B)
          {
              count++;
              count += FindCount(A, l, mid-1, B);
              count += FindCount(A, mid+1, r, B);
          }
          else if (A[mid] < B)
          {
              count = FindCount(A, mid+1, r, B);
          }
          else
          {
              count = FindCount(A, l, mid-1, B);
          }
      }
      return count;
 }

这应该可行，尽管它仍然是一个 O(n) 算法，效率不是很高。