繰り返し要素を持つ配列内の最大値を見つける

Question

配列の最大要素を最適に見つけることについて2日後のインタビューで質問がありました。

インタビュアーによって記載されているように、アレイは、整数値（連続する場所である必要はない）ことがありリピートから成り、それは、2つの部分（一方の部分は空であってもよい）からなる：非減少順で最初の部分、第2部はであり、増加していないのはです。 a [n]がn個の整数値からなる配列である場合、a [i] < = a [i + 1]、i [1、m]、a [j]> = a [j + 1] j in [m、n]であり、mは1とnの間のどこかにある。さて、彼らはという配列の中で最大値が最も効率的に見つかるように頼んだ。

私は、いくつかの要素が繰り返される可能性があるため、分割と征服戦略を使って検索スペースを構成することはできないと主張しました。すべての要素が異なっていれば、最大でlg n時間を見つけることができます。バイナリ検索を使用します。しかし、どの要素が最大であるかを知るには少なくともn-1の比較が必要な少なくとも1つの入力シーケンスが存在する（おそらくすべての要素が同じである場合もある）。

面接官は、入力に何らかの制約を課すことができるかどうかを質問して、lg n時間に問題を解決できるかどうかを尋ねました。私はその時に解決できず、まだ考えていませんでした。

あなたが私の考えを助けることができれば役に立ちます。

Answer 1

ternary searchについて知っているかどうかを調べようとしていました。部品が厳しく増加してから厳しく減少する必要がある場合は、Log3(N)で答えを得ることができます。インタビュアーが求めている追加の要件は、重複しているエントリがあれば、昇順降順の切り替えポイントの異なる側で発生するはずです。