分治算法计算数组中元素的外观，而不进行排序

Question

我和朋友在讨论是否可以在不排序数组的情况下，使用分治算法计算数组a[1…n]中出现的某个元素k的数量？

我们遇到了一个障碍，如果我们使用二进制搜索，一旦找到元素，它就会停止。有什么想法吗？

Answer 1

正如其中一条评论所提到的，二进制搜索用于在排序数组中查找一个元素，而在您的问题中似乎并非如此。

一个简单的分治算法将是将数组分解为更小的部分，并解决它们上的问题。例如，如果算法的输入是中的数组和valuek，您可以编写一个函数，将数组除以二并计算每个部分中出现的次数，然后将它们相加。

此函数获取给定向量中的左和右值。最初使用left=0和right=in调用此函数。size（）：

int NumberOfOccurances(const vector<int> &in, int k, 
                       int left, int right){
   // Base case when the size of the array is 1:
   if(right - left==1){
     return in[0] == k ? 1 : 0;
   } else {
     // Otherwise, break it into two subproblems.
     int mid = (left + right) / 2;
     return NumberOfOccurances(in, k, left, mid) +
            NumberOfOccurances(in, k, mid, right)
   }
}

除2之外，还可以除3、4或其他整数值。