データ構造とアルゴリズム論
第６章 探索のアルゴ
リズム
平成27年6月19日
森田 彦
理解度チェック１（問題１）
空欄①～③には以下のどの順で数字が並びます
か？適切な並びを選択して下さい。
１．4
４．3
3 8
8 4
２． 4
５． 8
8 3
3 4
３． 3
4 8
理解度チェック１ 解答
空欄①～③に入る適切な並びは？
１．4 3 8
４．3 8 4
２． 4 8 3
５． 8 3 4
３． 3 4 8
A 0 1 2 3
４ ３ ８ １
A[1]とA[2]を比較し、A[1]＜A[2]
なので交換する。
①
４ ②
８ ③
３ １
理解度チェック２（問題２）
空欄①～⑤には以下のどの順で数字が並びます
か？適切な並びを選択して下さい。
１．12
２．12
３．12
４．12
10
10
10
10
7
7
9
9
5
9
5
7
9
5
7
9
理解度チェック２ 解答
空欄①～⑤に入る適切な並びは？
１．12 10 7 5 9
３．12 10 9 5 7
２． 12 10 7 9 5
４． 12 10 9 7 9
A 0 1 2
10 12 7
3
5
4
9
12 12
10 7 5 9
i=0 10
i=1 12 10 7 5 9
i=2 12 10 79 5 79
理解度チェック３（問題３）
空欄①に入る最も適切な数値は次のいずれです
か？
１．2
２． 3
３．4
４．5
５． 6
理解度チェック３ 解答
空欄①に入る最も適切な数値は次のいずれです
か？
１．2
２． 3
３．4
４．5
５． 6
 iの初期値は、整列済み配列の末端の
要素番号。
 今の場合、A[3]までが整列済み。
 したがって、答は３。
探索とは？
 あるデータ群から、目的のデータと合致す
るものを探し出す、という処理。→検索と
も言う。
Webページの検索機能の強化→現在急速
に発展
本章では、最も基本的な探索アルゴリズム
を学習。
本章（本日）の学習のねらい
① 基本的な探索アルゴリズムを学習し、そ
の処理の流れを理解する。
→ 線形探索、2分探索
② 探索アルゴリズムの効率について考察
する。
③ 探索アルゴリズムを実際のプログラムに
応用する。
6-1 線形探索
 端から順番に探索する方法
例：カードの中から数字の３を探す。
５
１
３
３を発見！
流れ図で表すと・・・ → p.98参照
開始
＜線形探索のアルゴリズム＞
A[1]～A[n]にデータ保管済み
Noの入力 探したい数字を入力
データの終端のチェック
i←1
毎回必要？
i≦n
No
Yes
A[i] ＝No
Yes
’ありませんでした。’
No
i ← i+1
i,’番目にありました。’
次をめくる
終了
最大（2n+1）回の比較が必要 → 改良の余地は？
→ 番兵法へ（p.99）
＜番兵法のアルゴリズム＞
開始
A[1]～A[n]にデータ保管
Noの入力
i←1
A[n+1] ← No
データ終端を見分ける番兵の用意
データの終端のチェック
A[i] ＝No
No
i ← i+1
Yes
最後の1回だけ！
i≦n
No
Yes
’ありませんでした。’
i,’番目にありました。’
終了
最大比較回数が減った！
【基礎課題6-1】(p.100)
 データ数がｎ個の時の、最大比較回数
（データが見つからなかった場合の比較
回数）は？
線形探索法では、（２ｎ+1）回
番兵法では n+2 回？ (n+1)+1
流れ図の確認→【基礎課題6-2】（ループ端記号の場合）
【基礎課題6-3】（A[0]～A[n-1]の場合）
線形探索の（練習）プログラム→【基礎課題6-4】（p.103）
6-2 2分探索
 線形探索では、データ数に比例して（デー
タ照合のための）比較回数が増大。
 データ数が10倍→計算時間も10倍
→ 大きなデータ数では、効率が悪い！
 もっと効率の良い方法は？
2分探索法
例：数字「30」の書かれたカードを探す。
※最初に昇順にソートしておく。
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]
1
3
7 12 13 14 20 22 30 41
①
② 「30」と真ん中のA[5]を比較
③
「30」と真ん中のA[8]を比較
「30」とA[9]を比較
1
3
7 12 13 14 20 22 30 41
「30」がA[9]にあることを発見！→
探索範囲がA[9]～A[10]に絞られる。
探索範囲がA[6]～A[10]に絞られる。
終了！
データ数が2倍になっても比較回数は１回増えるだけ！
→ 【基礎課題6-5】で確認
流れ図の確認→p.107
プログラムは【基礎課題6-6】で作成
6-3 アルゴリズムの効率
２分探索法は線形探索法（番兵法）より効率
が良い。
p.110をよく読んで下さい。
【基礎課題6-5】をきちんとやっておくことが必要。
6-4 応用課題
 線形探索の応用→【応用課題6-A】
 ２分探索の応用→【応用課題6-B】
 【応用課題6-B】のプログラムを作成する
事ができれば、本章の理解度はOKです。
今後の予定
 6/26
 7/ 3
 7/10
 7/17
第７章 再帰処理
第８章 連結リスト
第９章 木構造
第１０章 スタックとキュー
 7/24 第２回テスト & 課題最終チェック
学習に当たって
 これまでの基礎課題を全て終了した学生
は【応用課題6-A】および【応用課題6-B】
のチェックを終了すれば演習を終えても
結構です。

データ構造とアルゴリズム論

データ構造とアルゴリズム論

データ構造とアルゴリズム論