c++ - 搜索排序数组中出现次数超过一半的元素所需的最少比较

Question

最近，我得到了一个问题，要找到从 n 给定元素中搜索元素所需的最少比较，前提是它们是排序，并且超过一半(n/2) 次。

例如。给定排序数组:1,1,2,2,2,2,2,7,11。此数组的大小为:9。我们需要找到找到 2 所需的最少比较(因为它出现的次数超过 n/2 次(5)。

这样做的最佳算法是什么？最坏情况下的复杂度是什么？

提供的选项是:

我)O(1)

ii) O(n)

iii) O(log(n))

iv) O(nlog(n))

Answer 1

provided they are sorted

在这种情况下你只需要检查一个中间元素，如果是的话

with more than half(n/2) occurrences

保证