time-complexity - 在所有元素相等的数组中进行二进制搜索

Question

我遇到了二进制搜索的问题。我正在做的事情如下： -

给定一个排序数组 arr[ ] 和一个数字 x 计算 x 在 arr[ ] 中的出现，以有效方式实现此逻辑的函数将需要????

答案是O(log(n))当我使用二进制搜索时，但是我有一个所有元素都相等的数组 arr[]，那么我将无法及时得到答案O(log(n))。这将花费 O(n) 时间。

现在我声称实现这个问题的有效算法需要O(n)时间。我的主张成立吗？

Answer 1

好吧，有效的算法是：

1. 找到第一次出现 x 的索引。
2. 找到 x 最后一次出现的索引。
3. 答案是 (2) - (1) + 1

这仍然是 O(log n)。