更好的算法用于查找元素的重复次数,给定一个排序数组,其中元素重复任何否.时间

Question

我已经尝试对给定元素进行二元搜索并向左和向右遍历它直到它得到比它更大或更小的元素,但是如果所有元素都相同则直到O(n)时间复杂度.可以有更好的算法吗？

Answer 1

您可以使用二进制搜索来查找范围的下限(和/或上限),并对下限进行二进制搜索,并且可以使一个元素范围的上限或下限大于你关心的一个.

编辑:我发现找到下限的大部分代码(我相信)比实际需要的要复杂得多.

int *find(int *left, int *right, int val) {
    assert(left<right);
    while (left < right) {
        int *middle = left + (right - left) / 2;
        if (*middle < val)
            left = middle + 1;
        else
            right = middle;
    }
    return left;
}