この問題を解決するのに苦労しています。
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)
すでに指摘されている「埋められたゼロ」の最悪のケースにもかかわらず、p、q に応じて、多くの場合高速化できるアルゴリズムを実装することをお勧めします。たとえば、n 個の数値があり、各増加領域と減少領域のサイズが少なくとも k であるとします。次に、配列内の 2^m 要素をチェックすると、最初と最後の要素、および残りの要素をできるだけ等間隔に配置し、m=2 から開始して、m を 1 ずつ繰り返し増加させると、最終的には m に到達します。チェックした 2^m 個の要素のうち、A < B, C > D を満たす連続した要素 (A,B),(C,D),(E,F) の 3 つのペアを左から右に見つけます、E < F (一部のペアは要素を共有する場合があります)。私の封筒の裏側の計算が正しければ、これを達成するために必要な最悪の場合の m は、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 を満たす連続したチェック済み要素 (A,B),(C,D) の 2 つのペアがあり、連続したチェック済み要素 (W,X),(Y の 2 つのペアもあります。 ,Z) W > X を満たす配列の後半、Y < Z. A の前のすべてが増加し、D と W の間のすべてが減少し、Z の後のすべてが増加します。したがって、配列内のこれら 3 つの領域をバイナリ検索できます。完全に検索していない配列の残りの部分のサイズは O(sqrt(n)) であるため、チェックされていない領域を総当たり検索することができ、全体の実行時間は O(sqrt(n)) です。したがって、一般的には O(n/k + sqrt(n)) という境界が成り立ちます。これが最悪の場合の最適であると感じていますが、証拠はありません。そのため、チェックされていない領域を総当たり検索することができ、全体の実行時間は O(sqrt(n)) です。したがって、一般的には O(n/k + sqrt(n)) という境界が成り立ちます。これが最悪の場合の最適であると感じていますが、証拠はありません。そのため、チェックされていない領域を総当たり検索することができ、全体の実行時間は O(sqrt(n)) です。したがって、一般的には O(n/k + sqrt(n)) という境界が成り立ちます。これが最悪の場合の最適であると感じていますが、証拠はありません。