問題タブ [linear-search]

線形検索と二分検索の違いは何ですか？

私はこの線形検索を最適化しようとしています:

配列はソートされ、関数はキー以上の最初の要素のインデックスを返すことになっています。They 配列は大きくなく (200 要素未満)、多数の検索に対して一度だけ準備されます。n 番目以降の配列要素は、必要に応じて適切なものに初期化できます。これにより、検索が高速化されます。

いいえ、バイナリ検索は許可されていません。線形検索のみが許可されています。

編集: このトピックに関する私の知識はすべて、このブログ投稿にまとめられています。

ソートされていない配列データ構造でアイテムを見つけるための平均ステップ数がN/2である理由を誰かが説明できますか？

決定論的線形探索アルゴリズムの平均ケース実行時間を導き出そうとしています。アルゴリズムは、ソートされていない配列Aの要素xをA [1]、A [2]、A [3] ...A[n]の順序で検索します。要素xが見つかると停止するか、配列の最後に到達するまで続行します。ウィキペディアで検索したところ、答えは（n + 1）/（k + 1）でした。ここで、kはxが配列に存在する回数です。私は別の方法でアプローチし、別の答えを得ています。誰かが私に正しい証拠を教えてくれ、また私の方法の何が悪いのか教えてもらえますか？

単純化しても（n + 1）/（k + 1）が得られません。

C の線形検索から複数の検索を出力するにはどうすればよいですか?

たとえば、配列にターゲットと等しい複数の要素がある場合、複数の値を返すことは可能ですか?

検索でバイナリ検索と while ループと for ループの両方を使用してみましたが、同じ問題が発生しています。

私の元のプログラムがこの関数呼び出しに来ると、線形検索関数 (displayContent) は常に位置に -1 を割り当て、関数呼び出しの後、プログラムは中断して終了します。

私は自分のプログラムを再編成しようとしました。私が言ったように、二分探索と線形探索の両方で for ループと while ループを試しました。

の構造データ型も使用しています

これが私の関数呼び出しです

ここに私の関数定義があります

ハッシュテーブルルックアップと線形検索のパフォーマンスを比較してみました。1000個のアイテムを含むハッシュテーブルを作成し、ハッシュテーブルでルックアップを実行するのにかかる時間が0.0002であることDateTime.Nowがわかりました（ルックアップの前後のシステム時間を調べて、それらを差し引いていました）。配列に同じ1000行があり、線形検索を使用して同じ値を検索しました。そして、それはハッシュテーブルのルックアップにかかる時間よりも短いことが判明しました。

ハッシュテーブルは線形検索よりも高速だと思いました。それはどのように機能しますか？

プログラムにコンパイル エラーはありませんが、出力が正しくありません。入力例:

配列のサイズ: 5
入力数値: 5 4 3 2 1
//ソート済み: 1 2 3 4 5
検索: 1
出力: インデックス 4 で見つかった数値 1

番号はすでにソートされているため、出力はインデックス 0 で見つかった番号 1 になるはずです。これをどう変えるか。

items10000個のソートされたランダムint値を持つ配列でシーケンシャル検索とバイナリ検索を実行するプログラムを作成しようとしています。呼び出された 2 番目の配列には、1000 個の値 (配列からの500 個の値と、配列にない 500個の値)targetsがロードされます。intitemsitems

int基本的に、検索では配列内の値を探すために項目配列を通過する必要がありますtargets。これは私のコードです:

編集：出力はこれでなければなりません>

395

986

-1

14

-1

シーケンシャル検索時間: 40 ミリ秒

395

986

-1

14

-1

バイナリ検索時間: 0 ミリ秒

私が取り組んでいる問題について質問があります。ビデオを繰り返さずに順番にランダムにビデオを再生する必要があります。各動画は、プレイリストごとに 1 回だけ再生できます。各ビデオには、0 から max_video_count までの一意の ID があり、これは実行時に決定されます (サーバーによって異なります)。

私が今やっていることは、再生された各ビデオの一意の ID を追加するリンク リストを作成したことです。0 と max_video_count の間の乱数をランダムに作成するよりも、数値がリンク リストに既にある場合は線形検索を実行し、そうであれば新しい数値を計算します..そして再び線形検索..などなど!!

明らかに、これはあまり実用的ではなく、要素を見つけるのに時間がかかる場合があります。特に、すでに多くの動画が再生されている場合。

だから私は考えました、私は線形検索の代わりに二分検索を実装しますが、それは私が最初にリストをソートしなければならないという問題に私をもたらします。したがって、私の次のステップは、新しいunique_idを挿入しながらリストをソートし、バイナリ検索を行うことだと考えることでした。

二分探索は O(n) 線形探索と比較して O(log n) であることを知っています。これは大きな進歩です。しかし、リストのソートもO(n)です。なぜなら、正しい場所を見つけるには、線形検索を再度実行する必要があるからです.... O(n) 線形検索 -> 線形検索高速。そうですか？たぶん私のアプローチ全体が間違っている..しかし、私はまだ何か良いものを思い付くことができませんでした...

私はアルゴリズムにまったく慣れていないので、誰かがここで私を啓発してくれるとうれしいです:-)

こんにちはマルクス