データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏 2007.12.13

第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

定義4.1 （探索） 探索とは，入力として n 個のデータ d0, d1, ... , dn-1 と値 x が与えられたときに，データ中から x = di となる di をみつける操作である． 探索する値がデータの中に存在しないときは， “データ中に存在しない”という出力を行う．

日常生活における探索の例 辞書 n 個のデータ d0, d1, ... , dn-1 ：辞書に載っているすべての単語 探索する値 x ：調べたい単語 インターネット・オークション n 個のデータ d0, d1, ... , dn-1 ：オークションに出品されているすべての商品名 探索する値 x ：欲しい物の商品名

簡単な探索アルゴリズム 以降では，与えられる n 個のデータ d0, d1, ... , dn-1 ，および，探索する値 x は，すべて正の整数であると仮定する．

アルゴリズム4.1 （線形探索） 入力：n個のデータを格納する配列Dと探索する値 x i = 0; while (i < n) { if (x == D[i]) { D[i] を出力してアルゴリズムを終了; } else { i = i + 1; } “xは存在しない”と出力;

アルゴリズム4.1の実行例 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] D 17 39 1 9 5 24 2 11 23 6 13 29 28 20 15 33 23

アルゴリズム4.1の時間計算量 最良時間計算量は O(1) 最悪時間計算量は O(n) 平均時間計算量は O(n) [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] D 17 39 1 9 5 24 2 11 23 6 13 29 28 20 15 33 最良時間計算量は O(1) 最悪時間計算量は O(n) 平均時間計算量は O(n)

第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

2分探索法 入力データが昇順に（小さい順）に，配列D に格納 されていると仮定する: D[0] < D[1] < D[2] < ... < D[n-1].

2分探索法（１） 探索する値 x と配列の中央にあるデータと比較する． xと比較する D [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 探索する値 x と配列の中央にあるデータと比較する．

2分探索法（２） 中央のデータと x が等しい場合，そのデータを出力して 探索を終了する． D[7] == x の場合 D [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 中央のデータと x が等しい場合，そのデータを出力して 探索を終了する．

2分探索法（２） 中央のデータが x より小さい場合，x は中央のデータより左側にはないので，探索範囲をD[8]～D[15]に限定できる． D[7] < x の場合 D [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 中央のデータが x より小さい場合，x は中央のデータより左側にはないので，探索範囲をD[8]～D[15]に限定できる．

2分探索法（３） 中央のデータが x より大きい場合，x は中央のデータより右側にはないので，探索範囲をD[0]～D[6]に限定できる． [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] 中央のデータが x より大きい場合，x は中央のデータより右側にはないので，探索範囲をD[0]～D[6]に限定できる．

2分探索法の実行例(x=23) D[7] < 23 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

2分探索法の実行例(x=23) 23 < D[11] D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

2分探索法の実行例(x=23) D[9] < 23 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

2分探索法の実行例(x=23) D[9] == 23 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

2分探索法の実現（アルゴリズム4.2） 入力: n個の昇順データを格納する配列 D と探索する値 x left = 0; right = n -1; mid = (left + right)/2; while (left < right) { if (D[mid] == x) { D[mid]を出力しアルゴリズムを終了; } else if (D[mid] < x) { left = mid + 1; } else { right = mid -1; } mid = (left + right) /2; } if (D[mid] == x) { D[mid] を出力; } else { “x は存在しない”と出力; }

アルゴリズム1.3の動き 1回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 2回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 3回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39 4回目 D 1 2 5 6 9 11 13 15 17 20 23 24 28 29 33 39

２分探索法の時間計算量 調べる配列の大きさは， whileの繰り返しごとに，半分以下になる．したがって，k 回目のwhileの繰り返しを実行したときに，配列の大きさは 以下になる．

２分探索法の時間計算量（続き） したがって，アルゴリズムが終了するまでのwhile文の繰返し回数 k は を満たす． 上式を書き換えると，　　　　　 であるから， を得る． したがって，最悪時間計算量は O(log n) である．

第4章データの探索 4.1 探索の定義と簡単な探索アルゴリズム 4.2 2分探索法 4.3 ハッシュ法

ハッシュ法のアイデア データを格納するおおまかな場所を，そのデータがもつ情報から決定する． 部屋番号----> 部屋番号の左端の数字 ４０３だから４階だな データを格納するおおまかな場所を，そのデータがもつ情報から決定する． 部屋番号----> 部屋番号の左端の数字

ハッシュ関数 データ x から，そのデータを格納する大まかな場所を決定する関数をハッシュ関数呼んで，hash(x) と表す． 例） x　----> hash(x) = (x の左端の数字）

データを格納するための配列 H データを格納する場所として，配列Hを準備する． ハッシュ法で用いる配列のサイズは格納するデータのサイズ n の 1.5～2倍とするのが一般的である． ここでは，Hのサイズは，1.5nとしておく．

ハッシュ法によるデータの格納の例 データの集合 {17, 39, 1, 9, 5,24, 2, 11, 23, 6, 13, 29, 28, 20, 15, 33} を考える．（n=16) データを格納するための配列 H のサイズは 16×1.5 =24 hash(x) = (x を 24で割った余り）= x%24 H [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]

アルゴリズム4.3 （ハッシュ法によるデータの格納） 入力：サイズ m のH，および，n個のデータを格納する配列D for (i=0; i<n; i = i+1) { k = hash(D[i]); while (H[k]にデータが格納されている) { k = (k+1)を m で割った余り; 　 } H[k] = D[i]; }

アルゴリズム4.4 （ハッシュ法による探索） 入力：アルゴリズム4.3によりデータの格納された配列Hと探索する値 x k = hash(x); while (H[k]にデータが格納されている) { if (H[k] == x) { H[k]を出力してアルゴリズムを終了; } k=((k+1)をmで割ったあまり; “xは存在しない”と出力;

宿題 第4章の演習問題の全て．（提出しなくてもよい．巻末の解答例を見て自己採点せよ．）

お知らせ http://coconut.sys.eng.shizuoka.ac.jp/algo/07/ 2007年12月20日(木）のこの時間帯に中間試験を行う． 詳細はWebページ http://coconut.sys.eng.shizuoka.ac.jp/algo/07/ に掲載予定です．