5

C (標準ライブラリ) で bsearch() を使用すると、ソートされた配列内のエントリをすばやく見つけることができます。

ただし、(標準ライブラリを使用して) 新しいエントリを挿入する場所を計算するにはどうすればよいですか?

bsearch() は、見つかったアイテムのキーが渡されたキーと等しいかどうかを具体的にチェックし、そうでない場合は NULL を返すため、使用できません。

4

4 に答える 4

5

質問からは明らかではありませんが、おそらくこれがあなたが望むものです:

このようなことを実行してbsearch ()、一致が見つかった配列内のインデックスを見つけることができます。

if (bsearch_returned_address != NULL)
  index = (bsearch_returned_address - array_base_address)

編集

bsort が最後に訪れた場所を知るには、以下をチェックしてください。

良いことは、マニュアルに次のように記載されていることです。

compar ルーチンは、キー オブジェクトと配列メンバーをこの順序で指す 2 つの引数を持つことが期待され、キー オブジェクトが見つかった場合はそれぞれゼロより小さい、等しい、または大きい整数を返す必要があります。配列メンバーより小さい、一致する、または大きい。

したがって、比較関数内の 2 番目の引数をグローバル変数に格納できます。失敗した場合は、この変数のアドレスを使用します。これは、bsearch関数が一致を見つけるために最後にアクセスした場所を指します。

例えば：

アドレスと値のリスト:

[0x8d6010: 0][0x8d6014: 4][0x8d6018: 8][0x8d601c: 12][0x8d6020: 16][0x8d6024: 20][0x8d6028: 24][0x8d602c: 28][0x8d6030: 32][0x8d6034: 36]

検索する値

13

出力

fmem: (nil)  //this is the memory location where it was found
last_mem1: 0x7fff8c8e6c54 //last val of 1st param of compare
last_mem2: 0x8d601c //last val of 2nd param of compare
*last_mem1: 13,        *last_mem2: 12

サンプルの比較関数コードは次のとおりです。

static const int *last_mem1, *last_mem2;

static int
compmi(const void *a, const void *b)
{
    last_mem1 = a; last_mem2 = b;
    return *(int *)a - *(int *)b;
}

そのため、 のアドレスの後に挿入できますlast_mem2。最終的なケースもありますが、最初の要素よりも小さいキーが見つかった場合は、最初の要素last_mem2のアドレスも含まれます。

しかし、挿入の場所を作るために配列要素をシフトする必要がある場合は、挿入が複雑になりO(n)ます。元のリストよりもはるかに小さい別の順序付けられていないリストを作成し、そこに新しい要素をダンプするなど、ある種の遅延挿入を導入してパフォーマンスを向上させたい場合があります。検索するときは、元のリストで実行bsearchし、ダンプで線形検索を実行します。ダンプ リストが特定のしきい値を超えて大きくなると、挿入ソートを実行してリストをマージできます。しかし、それでも、あなたはできませんO(lg n)。

于 2012-06-28T12:59:47.097 に答える
1

insert は配列の末尾をコピーするため、時間は O(n) です。したがって、単純な線形検索によってコードが劇的に遅くなることはありません。配列の最後から検索を開始すると、検索中にアイテムをコピーすることもできます。

于 2012-06-28T13:26:42.853 に答える