データ構造とアルゴリズム
(第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の時間計算量
[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と比較する
D
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12][13] [14][15]
探索する値 x と配列の中央にあるデータと比較する．
2分探索法（２）
D[7] == x の場合
D
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12][13] [14][15]
中央のデータと x が等しい場合，そのデータを出力して
探索を終了する．
2分探索法（２）
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 < D[7] の場合
D
[0] [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
5
6
9 11 13 15 17 20 23 24 28 29 33 39
2
5
6
9 11 13 15 17 20 23 24 28 29 33 39
2
5
6
9 11 13 15 17 20 23 24 28 29 33 39
2回目
D 1
3回目
D 1
4回目
D 1
２分探索法の時間計算量
調べる配列の大きさは， whileの繰り返しごとに，半分
以下になる．したがって，k 回目のwhileの繰り返しを
実行したときに，配列の大きさは
k
1
n
2
以下になる．
２分探索法の時間計算量（続き）
したがって，アルゴリズムが終了するまでのwhile文の
繰返し回数 k は
k
1
n 1
2
を満たす．
k
上式を書き換えると， n 2 であるから，
log n 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章の演習問題の全て．（提出しなくてもよい．巻末
の解答例を見て自己採点せよ．）
お知らせ
2007年12月20日(木）のこの時間帯に中間試験を行う．
詳細はWebページ
http://coconut.sys.eng.shizuoka.ac.jp/algo/07/
に掲載予定です．
© Copyright 2024 ExpyDoc
