うさぎでもわかる探索アルゴリズム 線形探索・2分探索・ハッシュ探索
友1「ねぇねぇ、今日のテスト何点だった？」友2「教えないよ。」友1「ちぇっ。なら今日のテスト50点以上とれた？」友2「うん。」(点数の範囲：50点〜100点)友1「なら75点以上は？」友2「取れてるよ。」(範囲：75点〜100点)友1「なら88点以上は？」 友2「取れてないよ。」(範囲：75点〜88点)友1「じゃあ82点以上？」友2「うん。さっきからしつこいなぁ。」(範囲：82点〜88点)友1「あ、もしかして85点？？」友2「なんでわかったの!? 怖！」
もう少し丁寧に書くと、 目的のデータとの大小を比べることでデータを探し出すアルゴリズム が 2分探索 です。
データの大小を利用して探すので、 あらかじめデータが小さい順（昇順）もしくは大きい順（降順）にソートしておく 必要があります。
このように2分探索は、 データを半分ずつにしぼりこんでいくので 線形探索よりも効率よく目的データの場所（有無）を調べることができます。
なお、プログラムでは探索範囲（データがありそうな場所）の先頭を left 、最後尾を right と表現します。
(2) 2分探索のプログラム要素数 n の配列 data から2分探索法でデータ x を探すプログラムは、下のようになります。
// 二分探索 データを半分ずつにしぼりこんで特定 // 二分探索 int binarySearch(int a[],int x) < int left = 0, right = N - 1; // 探索範囲 left 〜 right int mid; // 基準点 while(left else if(a[mid] < x) < left = mid + 1; // データを右半分にしぼり込む >else < right = mid - 1; // データを左半分にしぼり込む >> return -1; // 見つからなければ-1を返す > (3) 2分探索法の探索回数・計算量2分探索の場合、 データを半分ずつしぼりこみながら 探索します。そのため、 データ数が2倍になってはじめて探索回数が1回増えます ね。
データ数が1個の場合、必ず1回で見つけ出せるので n回の探索で \( 2^ \) 個のデータを探索することができます。
そのため、\( n \) 個のデータを探索するために約 \( \log_ n \) 回かかりますね。
計算量をオーダー表記で表すと、 \( O(\log n) \) となります*2。
４．ハッシュ探索
(1) ハッシュ探索とはハッシュ探索法は、 何かしらの計算式を用いて格納先を決めて格納する 探索方法です。
この「何かしらの計算式」を計算する関数のことを ハッシュ関数 と呼びます。
(2) ハッシュ探索の長所・短所ハッシュ関数は 専用の計算式からデータの格納先がわかる ため、原則 探索回数1回 でデータを見つけ出すことができます。
計算量をオーダーで表すとなんと \( O(1) \) です。
しかしいつもうまくいくとは限らず、 ハッシュ関数格納しようとした場所にすでにデータが存在し、衝突してしまうことがあります 。
- あきらめて別の計算で新しい格納先を決める
- 配列をもっと広く取って衝突の可能性を下げる
- 重複したデータをリストでつなげていく（チェイン法）
５．3つの探索法の比較
探索法計算量 ポイント 線形探索\( O(n) \)特になし。2分探索\( O(\log n) \)ソートの必要あり。ﾊｯｼｭ探索\( O(1) \)衝突しないことが条件。 探索アルゴリズムの比較- 線形探索法（ オーダー：\( O(n) \) ）→ 先頭から順番に地道にデータを探すアルゴリズム
- ２分探索法（ オーダー：\( O(\log n) \) ）→ データの大小から半分ずつしぼりこみ、データを探すアルゴリズム※ データがソートされている必要あり
- ハッシュ探索法（ オーダー：衝突しなければ \( O(1) \) ）→ ハッシュ関数と呼ばれる計算式からデータの格納先を探すアルゴリズム
６．練習問題
練習1ア：2分探索するデータ列は整列されている必要がある。イ：2分探索は線形探索より常に速く探索できる。ウ：2分探索は探索をデータ列の先頭から開始する。エ：n 個のデータの探索に要する比較回数は，\( n \log_ n \) に比例する。
練習2 練習3 練習4探索方法とその実行時間のオーダの正しい組合せはどれか。ここで、探索するデータ数をnとし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また，実行時間のオーダが \( n^ \) であるとは，n 個のデータを処理する時間が \( c n^ \) (cは定数) で抑えられることをいう。
2分探索線形探索ﾊｯｼｭ探索ア\( \log_ n \)\( n \)\( 1 \)イ\( n \log_ n \)\( n \)\( \log_ n \)ウ\( n \log_ n \)\( n^ \)\( 1 \)エ\( n^ \)\( 1 \)\( n \) 練習5 練習6（応用）７．練習問題の答え
解答1ア：正しい。ソートされているデータでないと2分探索はできない。イ：誤り。先頭にあるデータは線形探索では1ステップで求められるが、2分探索の場合は中央のデータを最初に探すので先頭にあるデータが1ステップで求められるとは限らない（というか低い）。ウ：誤り。先頭から探索を始めるのは線形探索。2分探索は中央のデータから探索を始める。エ：誤り。n 個のデータの探索に要する比較回数は \( \log_ n \) に比例する。
解答2 解答3 解答42分探索：データを半分ずつに絞り込めるのでオーダーは \( \log_ n \)線形探索：データを先頭から順番に探すので最大で n 回調べる必要がある。よってコーダーは \( n \)ハッシュ探索：専用の関数（ハッシュ関数）で求めるので1回で済む。ハッシュの衝突は無視できるのでオーダーは 1 となる。
解答5 解答61件目のデータ：10箇所どこに入れても衝突は起こらない。確率は12件目のデータ：1件目に入れた1箇所以外なら衝突が起こらないので確率は 9/10 = 0.93件目のデータ：1,2 件目に入れた2箇所以外なら衝突が起こらないので確率は 8/10 = 0.8
よって3件データを入れたときに衝突する確率は上の3つの積で求められるので、\[1 \times 0.9 \times 0.8 = 0.72\]と求められる。
「選択肢ア（0.28）だけやけに小さい確率だな…… もしかして、これ逆の確率（衝突する確率）なのかな…… ってことは答えはウの0.72……？？」
８．さいごに
*2 : オーダー表記の場合は定数の log は省かれることが多いです。基本情報では省かれていませんが……。
公開日： 2020年1月14日 更新日： 2021年5月27日 この記事を書いた人 コメント一覧 コメントはありません。 関連記事 4時間で復習！ オートマトンと言語理論 うさぎでもわかる線形代数 第15羽 固有値・固有ベクトル うさぎでもわかる離散数学 番外編1 数学的帰納法 うさぎでもわかる解析（高校数学・数3） Part07 置換積分：（中身の微分が被積分関数に含まれている場合の）置換積分の省略技 うさぎでもわかるソフトウェア工学 Part02 システム開発の工程の詳細 うさぎでもわかる離散数学（グラフ理論） 第19羽 彩色問題（地図を塗り分けてみよう！） うさぎでもわかる計算機システム Part02 2の補数表現 [基本情報対応] うさぎでもわかるオートマトンと言語理論 第02羽 非決定性オートマトン(NFA)の書き方・決定性オートマトン(DFA)への変換 うさぎでもわかるスタックとキュー うさぎでもわかる再帰関数のいろはカテゴリー
各種便利ツール・問い合わせ- 【完全無料】離散数学演習ツール・計算機まとめ
- 【ハッセ図】上界/下界・最大元/最小元・極大元/極小元・上限(最小上界)/下限(最大下界) 判定ツール
- 【ハッセ図】述語論理（∀・∃）真偽判定ツール
- 【離散数学】べき集合 2^A・P(A) 自動計算＆全列挙ツール
- 【離散数学】真理値表 自動作成ツール（途中式あり）
- 【離散数学】集合の「∈・⊆」真偽チェッカー（答え合わせ用）
- 【離散数学テスト対策】真理値表の穴埋めガチ演習ツール
- 【離散数学テスト対策】集合の「∈・⊆」ガチ演習！ 弱点分析つき○×ドリル
目次
工業大学生ももやまのうさぎ塾 (Momousagi Academy)