問題タブ [linear-search]

私のプログラムは完成しました。私が得た唯一のエラーは、二分探索と線形探索からのものです。それらは同じエラーなので、1つだけ投稿します。

まあ言ってみれば、

配列に 1000 個の要素があり、その配列内の 10 個の要素を検索したいのですが、どの検索メカニズムが最も適切ですか?

また、同じ配列から900個の要素を検索する必要がある場合、どの検索方法が良いですか?

線形または二分探索？

前もって感謝します。

文字列配列に順次/線形検索を書くことになっています。もうすぐ完成に近づいていますが、課題の一部で混乱しています。ターゲットが一致するか、ターゲットが配列の現在の要素よりも小さくなるまで、ターゲット項目をリストの連続する要素と比較するように指示します。数値がない場合、どのように文字列が別の要素よりも多くまたは少なくなることができますか? 多分私はそれについて正しく考えていないだけです。これまでの私のプログラムは次のとおりです。

最初の方法は問題なく機能しますが、リストにない要素の検索に問題があるようです。プログラムを実行した後に表示されるエラーメッセージは次のとおりです。

割り当てを理解し、例外を修正する助けをいただければ幸いです。

線形の方法 挿入する配列内の項目の位置を取得したいのですが、配列内のデータを挿入する必要があるインデックスを意味します。Linear search only を使用してこれを達成するにはどうすればよいですか。提案してください。

この質問は、線形検索の効率と、連続したストレージ内の事前に並べ替えられた配列のバイナリ検索の効率に関するものです...

Fortran (77!) で書かれたアプリケーションがあります。コードの一部で頻繁に行われる操作の 1 つは、配列内のインデックスを検索することgx(i) <= xin < gx(i+1)です。私は現在、これを次のように実装していますbinary search-- ステートメントのラベルについては申し訳ありませんが、- gotofortran 90 を使用すると、同等のステートメントがどのようなものになるかをコメントしました...

しかし、今日、ウィキペディアで二分探索について読んでいて、これに出くわしました。

私はこのステートメントを完全には理解していません.キャッシュフェッチは一度に大きな（っぽい）チャンクに集められたので、配列の先頭から開始すると、配列のほとんどがキャッシュにあると思いました.すでに（少なくとも線形検索の場合と同じくらい）、それが問題になるとは思いませんでした。

だから私の質問は、どちらのアルゴリズムがより優れたパフォーマンスを発揮するかを知る方法はありますか (線形検索またはバイナリ検索ですか?) 配列サイズの境界はありますか? 私は現在、約100要素のサイズの配列を使用しています...

私は、コレクションやコレクションのコレクションなどを検索するさまざまな方法をいじくり回してきました。私の理解を確認するために、愚かな小さなテストをたくさん行っています。これが私を困惑させるものです（ソースコードはさらに下にあります）。

つまり、N個のランダムな整数を生成し、それらをリストに追加しています。リストはソートされていません。次に、を使用Collections.contains()してリスト内の値を検索します。リストスペース全体がプローブされるようにしたいので、意図的にそこにないことがわかっている値を探します。私はこの検索の時間を計ります。

次に、別の線形検索を手動で実行し、リストの各要素を繰り返し処理して、ターゲットと一致するかどうかを確認します。私もこの検索の時間を計ります。

平均して、2回目の検索は最初の検索より33％長くかかります。私の論理では、リストはソートされていないため、最初の検索も線形である必要があります。私が考えることができる唯一の可能性（私はすぐに破棄します）は、Javaが検索のためだけにリストのソートされたコピーを作成しているということですが、（1）メモリスペースの使用を許可していませんでした。このような大きなNを使用すると、大幅な時間の節約になります。

したがって、両方の検索が線形である場合、両方とも同じ時間がかかるはずです。どういうわけか、Collectionsクラスはこの検索を最適化しましたが、その方法がわかりません。だから...私は何が欠けていますか？

編集：以下はこのコードの新しいバージョンです。興味深いのは、手動の線形ループがメソッドよりも16％高速に実行されるcontainsことです（注：どちらも意図的にリストスペース全体を検索するように設計されているため、反復回数が等しいことがわかります）。私はこの16％の利益を説明することはできません...もっと混乱します。

線形時間アルゴリズムを設計および解析して、n 個の要素のリストに、リスト内で少なくとも n/10 回繰り返される要素が存在するかどうかを判断します。

これどうやってするの？私は自分の考えを答えとして投稿しています。

クラスオブジェクトの配列を検索するように線形検索アルゴリズムを設定していますが、出力は一致しません。配列内の特定の名前を検索すると、配列内の1番目と3番目の値が見つかりますが、2番目の値は見つかりません。

以下は私のコードです。ご協力ありがとうございます。

チケットファインダーのように振る舞うと思われるプログラムを書いています。可能な座席の選択肢とその価格のチャートを表示し、ユーザーが座席を番号で選択するか価格で選択するかを尋ねます。番号で座席を指定すると思われるように機能しますが、価格で座席を見つけようとすると、配列インデックスが範囲外のエラーになります。ゼロから線形検索を開始すると想定されているため、混乱しています。このエラーが発生する理由がわかりません。

このプログラムは、整数が見つかったかどうか、および見つけるのにかかった時間を検出することになっています。1 つ目は線形検索で、2 つ目は二分検索です。私が抱えている問題はこれです。「線形検索が成功しました」というメッセージが何度も表示されることを除いて、線形検索は機能します。正直なところ、バイナリ検索で何も出力されない理由がわかりません。どんな助けでも大歓迎です