arrays - 查找一个数字是否在排序数组中出现 n/2 次的最小复杂度

Question

给定一个排序数组，是否有可能在 o(1) 中找到一个元素是否存在超过 n/2 次？如果中间元素不等于我们正在寻找的元素，那么我们可以肯定地说它存在少于 n/2 次或根本不存在。但是如果中间元素等于我们要找的元素，是否有可能找到它的出现次数是否超过 n/2 次？

Answer 1

我认为您正在查看 O(lg(n))。您需要进行二分搜索以查找元素的第一个和最后一个实例（假设该元素恰好出现 n/2 次）。

Answer 2

O(1) 并不意味着您只能搜索一次。这是表示小于固定常数的函数的渐近方法。

例如 3 是 O(1)，因此您可以搜索中间单元格及其两个相邻单元格，从而知道该元素是否至少存在 n/2 次。