在具有重复元素的数组中查找最大值

Question

两天前的一次面试中，我遇到了一个关于如何在数组中最佳地找到最大元素的问题，我对此有疑问。

面试官描述的数组由整数值组成，可以在连续的位置重复(不一定是在连续的位置)，它还包括两个部分(一部分可能是空的)：第一部分按不递减顺序排列，第二部分按非递增顺序排列，即如果一个数组由n个整数值组成，那么，ai<=ai+1，i in 1，m和aj>=aj+1，j in m，n和m位于1和n之间。现在，他们要求我以最有效的方式在数组中找到最大值。

我认为，由于某些元素可能被重复，我不能使用分而治之的策略来构成搜索空间。如果所有的元素是不同的，我们将能够找到最大的lg n时间使用二进制搜索。但是至少有一个输入序列(可能在所有元素都相同时)，我们至少需要对其进行n-1比较，然后才能判断哪个元素是最大的。

采访者要求我考虑是否可以对输入施加一些限制，以便在lg n时间内解决问题。当时我还没能解决，还在想。

如果你能帮我思考会很有帮助。

Answer 1

面试官想知道你是否了解三元搜索：如果你要求零件严格增加，然后严格减少，你就可以在Log3(N)中得到答案。因此，面试官寻找的额外要求可能是重复的条目，如果有的话，应该发生在上升-下降转换点的不同侧面。