两天前的一次采访中，我遇到了一个关于最佳地找到数组中的最大元素的问题，我对此有疑问。
面试官描述的数组由可能重复的整数值组成（不一定在连续的位置），它也由两部分组成（一部分可能为空）：第一部分按非递减顺序，第二部分按非递增顺序顺序，即如果a[n]是一个由n个整数值组成的数组，那么，a[i]<=a[i+1],i in [1,m] and a[j]>=a[j+ 1],j in [m,n] 和 m 介于 1 和 n 之间。现在，他们要求我以最有效的方式找到数组中的最大值。
我认为，由于某些元素可能会重复，因此我不能使用分而治之的策略来元素搜索空间。如果所有元素都不同，我们将能够使用二分搜索在lg n时间内找到最大值。但是至少存在一个输入序列（可能当所有元素都相同时），我们至少需要对其进行 n-1 比较才能判断哪个元素最大。
面试官让我想一想能不能对输入做一些限制，让问题能在lg n时间内解决。我当时没能解决，还在思考。
如果您能帮助我思考，那将很有帮助。