2分探索
白鷗大学 アルゴリズム論I
本日の講義内容
► コンピュータ内のデータの格納や処理方法
► 2分探索法
目次
► 引出しから数を見つけよう
(問題の説明)
引出しから数を見つけよう
► 書類を整理するための書類棚があります
► 書類棚には100個の引出しがついてます
► 引出しには1から100の番号がついています
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
31
.
.
.
40
...
...
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
引出しから数を見つけよう
► 書類を整理するための書類棚があります
► 書類棚には100個の引出しがついてます
► 引出しには1から100の番号がついています
► 各引出しには紙が1枚入っています
► 各紙には(各々異なる)数字が書いてあります
128
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
128
31
31
.
.
.
40
...
...
61
71
. .
.
.
543
. .
543
70
70
80
81
.
.
.
90
91
.
.
.
100
引出しから数を見つけよう
やりたい事:
► 書類を整理するための書類棚があります
 ある番号の紙が書類棚にあるかどうか調べたい
► 書類棚には100個の引出しがついてます
 例えば、「99」が書かれている紙が在るか無いか
► 引出しには1から100の番号がついています
► 各引出しには紙が1枚入っています
► 各紙には(各々異なる)数字が書いてあります
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
31
.
.
.
40
...
...
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
引出しから数を見つけよう
► 書類は次のように整理されて格納されている!
 2つの引出しを開けて中身の数字を比べたとき、
 引出し番号の大きい方(の数)が必ず大きい
2
30
121
30
11
11
64 128
64
21
21
128
31
31
. . . .
.
25 .
56 .
107 .
199
. . . .
25
10
10
56
20
20
30
30
107
40
40
199
...
...
501 555 604 656
501
61
61
555
71
71
604
81
81
656
91
91
. . . .
.
543 .
583 .
637 .
789
. . . .
543
70
70
583
80
80
637
90
90
789
100
100
目次
► 引出しから数を見つけよう
(問題の説明)
► 見つけ方をとりあえず考えてみよう
見つけ方をとりあえず考えてみよう
► 書類棚の問題を解く素朴な方法
 単純だが誰もが思いつく方法
►調べたい数字の紙が見つかるまで
►引出しを順々に調べていく
あったぞ
11
.
.
.
10
10
11
11
.
.
.
20
20
21
21
.
.
.
30
30
31
31
.
.
.
40
40
...
...
61
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
見つけ方をとりあえず考えてみよう
► 問題:この方法は効率的か?
書類棚の問題を解く素朴な方法
他に
もっと良い方法は
無いのか?
それを考えるには
何をどのように
考えればよいのか?
目次
► 引出しから数を見つけよう
(問題の説明)
► 見つけ方をとりあえず考えてみよう
► より良い方法を考えてみよう
より良い方法を考えてみよう
► 例えば、
数字が
►大きいそうなら100番目の引出しから
►小さそうなら1番目の引出しから
調べるのはどうだろうか?
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
31
.
.
.
40
100番目の
999を
999は
引出しから
探すぞ
大きそうだな
探し始めよう
... ... 9999...
61
...
.
.
.
70
71
.
.
.
80
81
げっ
91
. .
. .
. .
...
90
9999
100
100
より良い方法を考えてみよう
► より良い方法(「整理済み」という条件を使う)
► 基本となるアイディア
 効率良くするには?
⇒ 引出しを開ける回数を少なくすればよい
 開ける回数を少なくするには?
⇒ 開けても意味の無い引出しは開けない
 意味の無い引出しをどうやって見分けるのか?
⇒ 「整理済み」という条件を使う
より良い方法を考えてみよう
► より良い方法(「整理済み」という条件を使う)
► 引出しを開ける回数を51回以下にできるか?
 例えば、書類棚に555が在るか無いか調べたい
 そこで、50番目の引出しを開けたら500
?? だった
►あなたは49番目より前の引出しを調べますか?
⇒ 「調べる」と答えた人は修行を積み直して下さい
1
11
21
31
41
51
. . . . . .
こちらだけを調べればよい
. . . . .
500 .
.
.
. .
. .
10
20
30
40
50
50
60
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
より良い方法を考えてみよう
► より良い方法(「整理済み」という条件を使う)
► 引出しを開ける回数を51回以下にできるか?
 例えば、書類棚に555が在るか無いか調べたい
 そこで、50番目の引出しを開けたら600
500だった
►あなたは51番目より後の引出しを調べますか?
⇒ 「調べる」と答えた人は修行を積み直して下さい
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
31
.
.
.
40
41
51
. .
.
600 .
. .
50
50
60
61
71
81
91
. . . .
こちらだけを調べればよい
.
. . .
. . . .
70
80
90
100
より良い方法を考えてみよう
► より良い方法(「整理済み」という条件を使う)
► 引出しを開ける回数を51回以下にできるか?
⇒ できる
► 引出しを開ける回数をもっと少なくできるか?
► どこまで少なくできるのか?
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
31
.
.
.
40
41
.
.
.
50
51
.
.
.
60
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
より良い方法を考えてみよう
► 問題:
 引出しを開ける回数をもっと少なくできるか?
 できるとすると、どこまで少なくできるのか?
もっと減らせるかな?
どれだけ減らせるかな?
より良い方法を考えてみよう
► (今までの考察を基に)90を探してみよう!
 現時点の調査範囲は引き出し番号1~100まで
 調査範囲の真ん中辺りの50の引出しを調べる
こっちは
不用
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
31
41
. .
. .
123.
.
40
50
50
51
.
.
.
60
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
より良い方法を考えてみよう
► (今までの考察を基に)90を探してみよう!
 現時点の調査範囲は引き出し番号1~50まで
 調査範囲の真ん中辺りの25の引出しを調べる
こっちは
不用
1
.
.
.
10
11
21
31
.
.
.
. .
.
25
25
. . .
45 . .
.
20
.
.
.
30
40
41
.
.
.
50
より良い方法を考えてみよう
► (今までの考察を基に)90を探してみよう!
 現時点の調査範囲は引き出し番号25~50まで
 調査範囲の真ん中辺りの37の引出しを調べる
こっちは
不用
31
41
.
.
.
. .
37 .
.
37
105 . .
25
.
.
.
30
40
50
より良い方法を考えてみよう
► (今までの考察を基に)90を探してみよう!
 現時点の調査範囲は引き出し番号25~37まで
 調査範囲の真ん中辺りの31の引出しを調べる
あったぞ
90 31
31
25
.
.
.
30
.
.
.
37
より良い方法を考えてみよう
► 今見てきた「より良い方法」のポイント
 調査範囲を絞り込んでいく点
►[1~100]、[1~50]、[25~50]、[25~37]
100
50
26
13
 調査範囲の真ん中辺りを調べている点
►1~100の中央付近の50
1~50の中央付近の25
・・・
目次
► 引出しから数を見つけよう
(問題の説明)
► 見つけ方をとりあえず考えてみよう
► より良い方法を考えてみよう
► 見つけた方法を分析してみよう
見つけた方法を分析してみよう
► [素朴な方法]と[より良い方法]との違いは何?
 もし書類棚が「整理済み」でなかったとしたら?
►それでも[素朴な方法]はうまく働く
「違い」って言われてもな~
何をどう考えればいいの?
►それでは[より良い方法]はうまく働かない
 引出しを開けるたびに減る調査範囲の量は?
►[素朴な方法]では1回につき1個減る
►[より良い方法]では1回につきほぼ半分減る
 [1~100]、[1~50]、[25~50]、[25~37]
100
50
26
13
見つけた方法を分析してみよう
► [素朴な方法]と[より良い方法]の手間の差は?
 「引出しが、どんなに遠くにあったとしても
「差」って言われても と仮定する
ちょうど1秒で数字が確認できる」
ピンとこないな~
 引出しが1万個あった場合
►[素朴な方法]では最悪の場合2時間以上かかる
►[より良い方法]では最悪でも20秒以内ですむ
これ以降は予備のシート
より良い方法を考えてみよう
► より良い方法(「整理済み」という条件を使う)
► 基本となるアイディア
 調べる範囲の真ん中辺りの引出し(M)を調べる
 もし (調べたい数字) = (引出しMの紙の数字)
⇒ 発見したので作業を終了する
 もし (調べたい数字) > (引出しMの紙の数字)
⇒ 調べる範囲をMよりも引出し番号の大きい所に絞る
 もし (調べたい数字) < (引出しMの紙の数字)
⇒ 調べる範囲をMよりも引出し番号の小さい所に絞る
 上記の作業を調べる範囲が無くなるまで繰り返す
より良い方法を考えてみよう
► より良い方法(「整理済み」という条件を使う)
 調べる範囲の真ん中辺りの引出し(M)を調べる
 もし (調べたい数字) = (引出しMの紙の数字)
あったぞ
⇒ 発見したので作業を終了する
 もし (調べたい数字) > (引出しMの紙の数字)
⇒ 調べる範囲をMよりも引出し番号の大きい所に絞る
 もし (調べたい数字) < (引出しMの紙の数字)
⇒ 調べる範囲をMよりも引出し番号の小さい所に絞る
11
.
.
.
10
10
11
.
.
.
20
21
31
.
.
.
.
.
.
25
25
.
.
.
30
37
37
40
31
.
.
.
40
50
31
.
.
.
40
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
引出しから数を見つけよう!
► 問題:調べるときに以下のどちらが有利か?
整理されている方か?
それとも
どちらも変わらない
か?
手順(プログラム)を考えてみよう!
► 書類棚の問題を解く素朴なプログラム
 1番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進む
►調べたい数字と等しい
プログラムらしく書き直そう
似ている構造をまとめよう
 2番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進
►調べたい数字と等しい
3番目の引出しを調べる
5番目の引出しを調べる
4番目の引出しを調べる
・・・
 100番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進む
►調べたい数字と等しい
手順(プログラム)を考えてみよう!
► 書類棚の問題を解く素朴なプログラム
 1番目の引出しを調べる
XX番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進む
►調べたい数字と等しい
 2番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進む
►調べたい数字と等しい
・・・
 100番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進む
►調べたい数字と等しい
手順(プログラム)を考えてみよう!
 XX番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進む
►調べたい数字と等しい
...
手順(プログラム)を考えてみよう!
► 書類棚の問題を解く素朴なプログラム
 100番目の引出しを調べる
⇒ 「在る」と答え終了
►調べたい数字と等しくない ⇒ 次に進む
►調べたい数字と等しい
手順(プログラム)を考えてみよう!
► 書類棚の問題を解く素朴なプログラム
► 調べたい数を文字(記号)で表す
 1番目の引出しの数字が調べたい数と等しいか?
►YES
⇒ 「在る」と答え終了
►NO ⇒ 次に進む
 1番目の引出しの数字が調べたい数と等しいか?
►YES
⇒ 「在る」と答え終了
►NO ⇒ 次に進む
引出しから数を見つけよう!(1/4)
► 書類を整理するための書類箱があります
► 書類箱には100個の引出しがついてます
► 引出しには1から100の番号がついています
► 各引出しには紙が1枚入っています
► 各紙には(それぞれの)数字が書いてあります
1
.
.
.
10
11
.
.
.
20
21
.
.
.
30
128
31
31
.
.
.
40
...
...
61
.
.
.
543
70
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
引出しから数を見つけよう!(1/4)
► 書類を整理するための書類箱があります
► 書類箱には100個の引出しがついてます
► 引出しには1から100の番号がついています
► 各引出しには紙が1枚入っています
► 各紙には(それぞれの)数字が書いてあります
2
30
121
30
11
11
. .
.
.
25
56
. .
25
10
10
56
20
20
64 128
64
21
21
128
31
31
.
.
107
.
.
.
199
.
30
30
107
40
40
199
...
...
501 555 604 656
501
61
61
555
71
71
604
81
81
656
91
91
.
.
543
.
.
.
583
.
.
.
637
.
.
.
789
.
543
70
70
583
80
80
637
90
90
789
100
100
引出しから数を見つけよう!(1/4)
► 書類を整理するための書類箱があります
► 書類箱には100個の引出しがついてます
► 引出しには1から100の番号がついています
► 各引出しには紙が1枚入っています
► 各紙には(それぞれの)数字が書いてあります
2
121
.
.
.
25
10
10
30
11
11
.
.
.
56
20
20
64
21
21
.
.
.
30
30
107
128
31
31
.
.
.
40
40
199
...
...
656
501
61
61
.
.
.
543
70
70
555
71
71
.
.
.
583
80
80
604
81
81
.
.
.
637
90
90
656
91
91
.
.
789
.
789
100
100
より良い方法を考えてみよう
あったぞ
31
25
37
50
1
.
.
.
10
11
.
.
.
20
21
31
.
.
.
.
.
.
25
.
.
.
30
37
40
41
.
.
.
50
51
.
.
.
60
61
.
.
.
70
71
.
.
.
80
81
.
.
.
90
91
.
.
.
100
講義を振り返ってみて
より良い方法を考えてみよう
見つけ方をとりあえず考えてみよう
►
問題:この方法は効率的か?
►
他に
もっと良い方法は
無いのか?
問題:

引出しを開ける回数をもっと少なくできるか?

できるとすると、どこまで少なくできるのか?
もっと減らせるかな?
どれだけ減らせるかな?
それを考えるには
何をどのように
考えればよいのか?
見つけた方法を分析してみよう
►
[素朴な方法]と[より良い方法]との違いは何?
「違い」って言われてもな~
何をどう考えればいいの?
見つけた方法を分析してみよう
►
[素朴な方法]と[より良い方法]の手間の差は?
「差」って言われても
ピンとこないな~
そんな学生が自動車メーカーに就職したら
(おそらく止まるであろう・・・)
ブレーキが
あ
ほらね
コンピュータ制御
だから大丈夫
このとおりれ??
んぅ??
だっ、誰か
そんなに
止めてくれ!!
スピード出して
大丈夫?
ダウンロード

2分探索法