0

N が配列の長さである 0 から N-1 のオフセットを持つ並べ替えられた数値の配列があるとします。以下に示すように、完全にソートされた配列には 0 ゼロオフセットがあります

[1, 2, 4, 11, 15, 19, 26]

[19, 26, 1, 2, 4, 11, 15]小さい方の数が 2 番目のインデックスから始まり、最初のインデックスにラップアラウンドするため、配列のオフセットは 2 です。

割り当ての問題は、配列内の数値のインデックスを見つける方法です。ソートされた配列の場合、解決策は明らかにインデックスを見つけるためのバイナリ検索です（再帰の有無にかかわらず）。

オフセットのある配列内の数値のインデックスを見つけるにはどうすればよいですか? オフセットは不明です。解決策の概要を知りたいので、慣れ親しんだ言語で実装してみます。

4

1 に答える 1

0

三項探索で配列の最大要素を見つけます。X が配列の最大要素のインデックスであると仮定しましょう。したがって、オフセットは の場合は X+1 になりX < N-1、それ以外の場合はオフセット = 0 になります。

次に、各要素に対して 2 つのバイナリ検索を実行して、その番号のインデックスを見つけることができます。1 つ目は からの範囲で実行され0 - (offset-1)、2 つ目は の間で実行されoffset - Nます。より多くのスペースを使用できる場合は、配列をそれ自体に追加して、クエリごとに単一のバイナリ検索を行うこともできますoffset - (N+offset-1)

于 2013-08-18T19:34:53.037 に答える