アルゴリズムの授業 1. 線形探索 (Linear Search) 1.1 概要配列（またはリスト）の先頭から順番に目標値と比較し、一致したらその位置を返す。見つからなければ最後まで調べ終えて「未発見」を返す。 1.2 計算量最良ケース：O(1) … 先頭にあった場合平均ケース：O(n/2) ≒ O(n) 最悪ケース：O(n) … 存在しない場合や末尾にあった場合空間計算量：O(1) 1.3 特徴・利点・欠点利点ソート不要。要素の順序を問わない実装が非常にシンプル欠点要素数が大きいと比較回数も増大し、性能悪化頻繁に検索する場合は不向き 1.4 実装例 (C++) // 配列 arr[n] の中から key を線形探索し、見つかればそのインデックスを、 // 見つからなければ -1 を返す int linearSearch(const std::vector& arr, int key) { for (size_t i = 0; i < arr.size(); ++i) { if (arr[i] == key) { return static_cast(i); } } return -1; } 1.5 適用場面データ数が少ない、あるいは検索回数が少ない場合配列がソートされていない、かつソートコストをかけたくない場合 2. 二分探索 (Binary Search) 2.1 概要ソート済み配列の中央要素と比較し、目標値が小さければ左半分、大きければ右半分を再帰的（またはループ）に探索。範囲を半分ずつ絞っていく。 2.2 計算量最良・平均・最悪ケース：いずれも O(log n) 空間計算量：O(1)（ループ版）／O(log n)（再帰版のスタック分） 2.3 特徴・利点・欠点利点大量データでも高速欠点事前にソートが必要（ソートコスト O(n log n)）配列へのランダムアクセスが前提実装ミス（境界条件）でバグを生みやすい 2.4 実装例 (C++) // ソート済み vector の二分探索 int binarySearch(const std::vector& arr, int key) { int left = 0; int right = static_cast(arr.size()) - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == key) { return mid; } else if (arr[mid] < key) { left = mid + 1; } else { right = mid - 1; } } return -1; } 2.5 適用場面データが事前にソートされている検索回数が多く、毎回高速に探したい場合 3. ハッシュ探索 (Hash Search) 3.1 概要ハッシュ関数でキーからテーブルの領域（バケット）を計算し、直接アクセス。バケット内はリストや連想配列で衝突解消（チェイニング、オープンアドレスなど）する。 3.2 計算量平均ケース：O(1) 最悪ケース：O(n) … ただし適切なリサイズやハッシュ関数でほぼ起こらない空間計算量：O(n)（テーブルサイズに応じたオーバーヘッドあり） 3.3 特徴・利点・欠点利点平均O(1)で非常に高速キー → 値の対応に最適欠点メモリ使用量が増えるハッシュ関数の設計／衝突解消の実装が必要順序付き探索には向かない 3.4 実装例 (C++ 標準ライブラリ利用) #include // key -> value のマップを作成し、検索 int hashSearch(const std::unordered_map& mp, int key) { auto it = mp.find(key); if (it != mp.end()) { // 見つかったら値を参照できる return it->second; } // 見つからない throw std::out_of_range("キーが存在しません"); } 3.5 適用場面キーとデータをペアで管理したい場合頻繁に挿入・削除・検索を行う動的なデータ構造 4. 比較まとめ特徴線形探索二分探索ハッシュ探索前提条件なしソート済みなし平均時間計算量 O(n) O(log n) O(1) 最悪時間計算量 O(n) O(log n) O(n) 空間オーバーヘッドほぼゼロほぼゼロテーブル分あり実装の易しさ ◎（簡単） ○（やや注意） △（ハッシュ設計）用途小規模or単発探索大規模かつ静的動的なキー／値管理 5. 使い分けのポイントデータが小さく、一度だけ検索する → 線形探索データはソート可能／ソート済みで、繰り返し検索する → 二分探索キーと値の対応を高速に管理したい／挿入・削除も行う → ハッシュ探索もしそれぞれの詳しい応用例や、別の言語での実装例、あるいは木構造探索（B木・AVL木など）についてもご興味があれば、ぜひお知らせください。あなた: ぎりぎりＣ言語しか勉強していない人がわかる疑似言語表記で、それぞれのアルゴリズムを説明してみてほしい。 ChatGPT: 了解です！ C言語に慣れている人がすんなり読めるように、「 C言語風の疑似コード（変数宣言あり、for・if中心、関数呼び出しも明示）」で、以下3つの探索アルゴリズムを順に説明します。 🔍 1. 線形探索（Linear Search） ● 概要先頭から順番に調べていって、見つかったらその位置（インデックス）を返す。 ● 疑似コード（C風） int linear_search(int arr[], int size, int key) { int i; for (i = 0; i < size; i++) { if (arr[i] == key) { return i; // 見つかったのでその位置を返す } } return -1; // 最後まで見つからなかった } ● 説明ポイント arr … 探す対象の配列 size … 配列の要素数 key … 探したい値見つかると i を返す、見つからないと -1 🌓 2. 二分探索（Binary Search） ● 概要中央を調べて、半分ずつ範囲を狭めていく方法（※配列がソートされている必要あり） ● 疑似コード（C風） int binary_search(int arr[], int size, int key) { int left = 0; int right = size - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == key) { return mid; // 見つかった } else if (arr[mid] < key) { left = mid + 1; // 右半分を探す } else { right = mid - 1; // 左半分を探す } } return -1; // 見つからない } ● 説明ポイント left と right で調べる範囲を持っておく中央（ mid ）と key を比較 key が大きければ右、小さければ左に範囲を狭める 🔳 3. ハッシュ探索（Hash Search） ● 概要値（key）を使って、直接「探す場所（インデックス）」を計算する方法 → 計算式： index = hash_function(key) ※ここでは衝突がない簡易な例として説明します ● 疑似コード（C風：簡易ハッシュテーブル使用） #define TABLE_SIZE 10 int hash_function(int key) { return key % TABLE_SIZE; } int hash_table[TABLE_SIZE]; // 値を保存するテーブル void insert(int key) { int index = hash_function(key); hash_table[index] = key; // ※衝突処理は省略 } int hash_search(int key) { int index = hash_function(key); if (hash_table[index] == key) { return index; // 見つかった } else { return -1; // 見つからない or 衝突で上書きされた } } ● 説明ポイント key % TABLE_SIZE で場所を決める insert() で格納、 hash_search() で検索 ※衝突（同じ場所になること）を処理するには工夫が必要（例：線形探査など） ✨ 比較まとめ（覚えやすく）種類ソート必要速さ（目安）簡単さ特徴線形探索不要遅い O(n) ◎ 簡単一番素直な方法二分探索必要速い O(log n) ○ 普通中央から半分に絞っていくハッシュ探索不要速い O(1) △ やや難直接位置を計算して探す