logo

TechCodeview

検索アルゴリズム

検索アルゴリズム は、データのコレクション内の特定のアイテムを見つけるために使用されるコンピューター サイエンスの重要なツールです。これらのアルゴリズムは、データ構造内を効率的にナビゲートして必要な情報を見つけるように設計されており、次のようなさまざまなアプリケーションの基礎となっています。 データベース、ウェブ検索エンジン 、 もっと。

検索アルゴリズム

目次



検索とは何ですか?

検索は基本的なプロセスです。 データのコレクション内の特定の要素または項目を検索する 。このデータのコレクションは、配列、リスト、ツリー、その他の構造化表現など、さまざまな形式を取ることができます。検索の主な目的は、目的の要素がデータ内に存在するかどうかを判断し、存在する場合はその正確な位置を特定するか、取得することです。情報検索、データ分析、意思決定プロセスなどを含む、さまざまな計算タスクや現実世界のアプリケーションで重要な役割を果たします。

用語の検索:

対象要素:

検索では、データ コレクション内で検索したい特定のターゲット要素またはアイテムが常に存在します。このターゲットは、値、レコード、キー、またはその他の対象となるデータ エンティティである可能性があります。

サーチスペース:

検索スペースとは、ターゲット要素を検索するデータのコレクション全体を指します。使用されるデータ構造に応じて、検索スペースのサイズと構成が異なる場合があります。

複雑：

検索の複雑さのレベルは、データ構造と使用されるアルゴリズムに応じて異なります。複雑さは、多くの場合、時間とスペースの要件の観点から測定されます。

決定論的 vs 非決定論的:

いくつかの検索アルゴリズム 二分探索 、決定論的であり、明確で体系的なアプローチに従っていることを意味します。線形検索などのその他の検索は、最悪の場合に検索空間全体を調べる必要があるため、非決定的です。

DSA での検索の重要性:

  • 効率： 効率的な検索アルゴリズムにより、プログラムのパフォーマンスが向上します。
  • データの取得: 大規模なデータセットから特定のデータをすばやく検索して取得します。
  • データベース システム: データベースの高速クエリを可能にします。
  • 問題解決： 幅広い問題解決タスクに使用されます。

検索の用途:

検索アルゴリズムは、さまざまな分野にわたって数多くの用途に使用されています。一般的なアプリケーションをいくつか示します。

  • 情報検索： Google、Bing、Yahoo などの検索エンジンは、高度な検索アルゴリズムを使用して、Web 上の膨大な量のデータから関連情報を取得します。
  • データベース システム: 検索は、ユーザーのクエリに基づいて特定のデータ レコードを取得するためのデータベース システムの基本であり、データ取得の効率を向上させます。
  • 電子商取引: 電子商取引プラットフォームでは、ユーザーが好み、仕様、キーワードに基づいて商品を素早く見つけるための検索が重要です。
  • ネットワーキング： ネットワーキングでは、ネットワークを通じてパケットを効率的にルーティングし、最適なパスを見つけ、ネットワーク リソースを管理するために検索アルゴリズムが使用されます。
  • 人工知能： 検索アルゴリズムは、問題解決、ゲームプレイ (チェスなど)、意思決定プロセスなどの AI アプリケーションで重要な役割を果たします。
  • パターン認識： 検索アルゴリズムは、画像認識、音声認識、手書き認識などのパターン マッチング タスクで使用されます。

検索アルゴリズムの基本:

  • 検索の概要 – データ構造とアルゴリズムのチュートリアル
  • データ構造内での検索の重要性
  • 検索アルゴリズムの目的は何ですか?

検索アルゴリズム:

  • 線形探索
  • センチネル線形検索
  • 二分探索
  • メタバイナリ検索 |片側二分探索
  • 三項検索
  • ジャンプ検索
  • 補間検索
  • 指数関数的検索
  • フィボナッチ検索
  • ユビキタスバイナリ検索

異なる検索アルゴリズム間の比較:

  • 線形探索と二分探索
  • 内挿検索と二分検索
  • 二分検索が三分検索よりも好まれるのはなぜですか?
  • Sentinel Linear Search は通常の Linear Search よりも優れていますか?

検索アルゴリズムのライブラリ実装:

  • C++ STL のバイナリ検索関数 (binary_search、 lower_bound および upper_bound)
  • Java の Arrays.binarySearch() と例 |セット1
  • Java の Arrays.binarySearch() と例 |セット 2 (部分配列の検索)
  • Java の Collections.binarySearch() と例

検索に関する簡単な問題:

  • 配列内の最大の 3 つの要素を検索します
  • 足りない番号を探す
  • 整数の配列内の最初の繰り返し要素を検索します。
  • 欠落している繰り返し番号を見つける
  • ソートされた配列の検索、挿入、削除
  • ソートされたバイナリ配列内の 1 を数えます
  • 合計がゼロに最も近い 2 つの要素
  • 指定された差を持つペアを見つけます
  • 配列内の最大 (または最小) 個の要素
  • 行方向および列方向にソートされた 2D 配列内の K 番目に小さい要素
  • 3 つのソートされた配列で共通の要素を見つける
  • ソートされた配列の天井
  • ソートされた配列のフロア
  • 最初に増加し、次に減少する配列内の最大要素を見つけます。
  • サイズが n で数値が k の配列を指定して、n/k 回以上出現するすべての要素を検索します。

検索に関する中程度の問題:

  • ゼロ和を持つすべての三重項を検索します
  • すべての要素がその要素よりも小さくなり、その後ですべてが大きくなる要素を見つけます。
  • ソートされていない配列内の最大のペアの合計を見つける
  • 未ソート配列内の K 番目の最小/最大要素
  • ソートおよび回転された配列内の要素を検索する
  • ソートおよび回転された配列内の最小要素を検索します。
  • ピーク要素を見つける
  • 最小比較数を使用した配列の最大値と最小値
  • 指定された配列内の固定小数点を検索する
  • ファイルから k 個の最も頻繁に使用される単語を検索します。
  • 指定された値に最も近い k 個の要素を検索します
  • ソートされた配列と数値 x を指定して、合計が x に最も近い配列内のペアを見つけます。
  • ソートされた 2 つの配列から最も近いペアを見つけます
  • 指定された 3 つのソートされた配列から最も近い 3 つの要素を検索します。
  • 浮動小数点演算を使用しない有理数の二分探索

検索に関する難しい問題:

  • ソートされた 2 つの配列の中央値
  • サイズの異なる 2 つの並べ替えられた配列の中央値
  • ほぼソートされた配列で検索
  • ソートされた無限数の配列内の要素の位置を検索する
  • ソートおよび回転された配列を指定して、指定された合計を持つペアがあるかどうかを見つけます
  • 未ソート配列の K 番目の最小/最大要素 |最悪の場合の線形時間
  • ストリーム内で K 番目に大きい要素
  • ベストファーストサーチ (情報に基づいた検索)

クイックリンク：

  • 「練習問題」を検索する
  • 検索時の「クイズ」

推奨：

  • データ構造とアルゴリズムを学ぶ | DSA チュートリアル