c++ - 在Logn中查找排序数组中元素的频率

这可能吗？
我想出了这个：

void binary_search(int list[], int lo, int hi, int key, int* maxIndex, int* minIndex) {
    int mid;
    if (lo > hi) {
        printf("Key not found\n");
        return;
    }
    mid = (lo + hi) / 2;
    if (list[mid] == key) {
        counter++;
        if (*maxIndex == -1) {
            *maxIndex = mid;
            cout << "Init max" << endl;
        }
        if (mid > *maxIndex) {
            *maxIndex = mid;
            cout << "Change max" << endl;
        }

        if (*minIndex == -1) {
            *minIndex = mid;
            cout << "Init min" << endl;
        }

        if (mid < *minIndex) {
            *minIndex = mid;
            cout << "Change min" << endl;
        }
    }
    if (mid - 1 >= 0)
        if (list[mid - 1] == key)
            binary_search(list, lo, mid - 1, key, maxIndex, minIndex);
    if (mid + 1 <= hi)
        if (list[mid + 1] == key)
            binary_search(list, mid + 1, hi, key, maxIndex, minIndex);
}



int main() {
    int min = 10;
    int max = -1;
    int arr[] = { 1,1,3,3,3,3,4,7,8,9 };

    binary_search(arr, 0, 10, 3, &max, &min);
    cout << max - min + 1 << endl;
    cout << counter;
    return 0;
}

我所做的是，找到元素的第一个外观，最后一个外观并扣除索引，但是它是O（logn）吗？

似乎最坏的情况是O（n），因为在最坏的情况下递归公式是T（n）= 2T（n / 2）= O（n）;

我的问题是，是否可以在O（logn）中执行此操作，并且将如何实现？

最佳答案

在Logn中查找排序数组中元素的频率
  
  这可能吗？


是。


  我所做的是，找到一个元素的首次出现，最后一次出现并扣除索引


那是一个明智的算法。


  但是是O（logn）吗？


二进制搜索可以在O(log n)中实现，而2个二进制搜索可以在2 * O(log n) = O(log n)中实现。因此，所描述的算法可以在O(log n)中实现。

您的实现是否达到这种复杂性，是另一回事。但是在分析程序之前，请考虑其功能上的缺陷：如果键值最初不在mid点内，则输出将保持不变，并给出错误的结果。例如：尝试在示例中搜索1的频率。

如果分别实现两个二进制搜索，将更容易分析您的算法...而且它也可能会更快，因为简单的二进制搜索可以进行尾调用优化。

ps。无需重新实现二进制搜索。标准库已经提供了一个实现：std::lower_bound和std::upper_bound（以及std::equal_range可以完全满足您的要求）。

关于c++ - 在Logn中查找排序数组中元素的频率，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35587445/