部分的にソートされた配列をO（lgn）で検索する

Question

この問題を解決するのは苦労しています。

A[1..n] is an array of real numbers which is partially sorted: 
There are some p,q (1 <= p <= q <=n) so: 
A[1] <= ... <= A[p] 
A[p] >= ... >= A[q] 
A[q] <= ... <= A[n] 

How can we find a value in this array in O(lgn)? 
(You can assume that the value exists in the array) 

Answer 1

1からp、pからq、qからnの3つのバイナリ検索を行います。複雑さは依然としてO（logn）です。

我々はpとqを知らないので：

あなたはLOGN時間でこの問題を解決することはできません。 （p + 1 = qとA [q] = 0）が混在した正の数のソートされたリストがあるとします。この状況は、あなたが言及したすべての基準を満たします。ここで、ゼロがどこにあるのかを見つける問題は、サブO（n）時間では解決できません。したがって、問題はO（logn）時間では解決できません。

Answer 2

「埋め込まれたゼロ」の最悪のケースは既に指摘されていますが、p、qに応じて処理を高速化できるアルゴリズムを実装することをお勧めします。たとえば、n個の数値を持ち、それぞれの増減領域が少なくともk個のサイズを持つとします。次に、最初の要素と最後の要素、残りの要素を可能な限り等しく配置し、m = 2で始まり、mを1ずつ増加させると、配列内の2^m要素を調べると、m A < B、C> Dを満たす、チェックした2^m要素のうち左から右へ連続した要素（A、B）、（C、D）、（E、F） 、E < F（一部のペアは要素を共有することがあります）。エンベロープの計算が正しい場合、これを達成するために必要な最悪の場合は、4n/k以上の要素をチェックする必要があります。 k = 100の場合は、n個の要素すべてをチェックするよりもはるかに高速です。その後、Aの前のすべてと、Fの後のすべてがシーケンスを増やしています。バイナリ検索が可能です。さて、もしmが少なくともsqrt（n）の要素をチェックしたならば、AとFの間でブルートフォースサーチを行うことで仕上げることができ、全体の実行時間はO（n/k + sqrt（n ））。一方、最後のmがsqrt（n）要素よりも少ない要素をチェックした場合、sqrt（n）要素をチェックするまでmをさらに増やすことができます。次に、A < B、C> Dを満たす2組のチェックされた連続した要素（A、B）、（C、D）、およびチェックされた要素（W、X）、Y 、Z）を返します。その後、W> X、Y < Zを満たす配列内で、Aの前のすべてが増加し、DとWの間のすべてが減少し、Zの後のすべてが増加します。したがって、配列内のこれら3つの領域をバイナリ検索することができます。あなたが完全に検索していない配列の残りの部分は、サイズO（sqrt（n））を持っているので、チェックされていない領域をブルートフォース検索して全体の実行時間をO（sqrt（n））とすることができます。したがって、束縛されたO（n/k + sqrt（n））は一般的に成立する。私はこれが最悪の場合最適だと感じていますが、私には証拠はありません。

Answer 3

O（log n）で解くことができます。

1. 中点で傾きが減少している場合は、p..qの範囲です。
2. 中点で斜面が増加している場合は、1..pまたはq..nのいずれかになります。
   • 1.. mid pointとmid point..nの範囲で二分探索を行い、傾きが減少する値を求めます。それは範囲の1つでのみ見つかるでしょう。ここでは、中間点が位置するサブ領域のうち、どれが1..pとq..nであるかが分かります。
3. p..qの範囲に達するまで、ピークを持つ部分範囲のプロセスを繰り返します。
4. Divide and conquer algorithm applied in finding a peak in an array.
5. のアルゴリズムを適用して部分範囲内のピークを見つけると、1..p、p..q、q..nの範囲で3つのバイナリ検索を実行します。

==>全体の複雑さはO（ログ n）です。