事前にソートされた数値を持つ配列(線形フィールド)があります
[1, 2, 3, 4, 5, 6],
しかし、これらの配列は右に (k 回) シフトされています。
今その
[5,6,1,2,3,4], k = 2
しかし、私はkを知りません。配列 A のみ。
ここで、A の最大値を見つけるアルゴリズムが必要です (ランタイム O(logn) を使用)
二分探索の何かだと思いますが、誰か助けてもらえますか??
この問題は、「不連続点」、つまり6, 1
アレイ内のスポットのインデックスを見つけるという観点から言い換えることができます。次のように、バイナリ検索と同様のアプローチを使用して、繰り返し実行できます。
配列A
と 2 つのインデックス と をlow
取りhigh
、最初は と に設定し0
ますA.Length-1
。不連続点は と の間low
ですhigh
。
(low, high)
半分に分けます。中点を呼び出しmid
ます。とを比較A[low]
してください。ペアが 1 つだけ正しく順序付けられている場合は、エンドポイントを調整します。順序付けられているペアの場合は assign 、そうでない場合は assign 。両方の間隔が順序付けられている場合、答えはです。A[mid]
A[mid]
A[high]
low-mid
low = mid
high = mid
A[high]
O(LogN)
各ステップで問題のサイズが半分になるため、これは実行されます。
基本的に二分探索であることは間違いありません。
真ん中の数字を選びます。それが (現在のパーティションの) 左端の数値よりも小さい場合、最大の数値は左のパーティションにあります。それ以外の場合は、正しいパーティションにあります。
「k」が何であるかがわかっている場合は、配列を分割して再構築するか、k でオフセットする二分探索アルゴリズムを再実装することができます。
例えば、
int low = 0;
int high = array.length - 1;
while(low != high)
{
int test = (low + high)/2;
int testIndex = (test + k) % array.length;
if (array[testIndex] < wanted)
low = test;
else if (array[testIndex] > wanted)
high = test;
else
return testIndex;
}
またはそのようなもの。testIndex 変数は「k」だけオフセットされていますが、検索インデックス (低、高、およびテスト) はそれを認識していません。
PS., このコードにさらに安全性チェックを追加する必要があります (たとえば、'wanted' が配列にありません)。インデックスのオフセット部分を表示したかっただけです。