スライド 1

アルゴリズムとデータ構造
補足資料4-3
「2分探索」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
あらかじめ「昇順」に整列された配列
a[0]
a[1]
a[2]
a[3]
1
3
5
8
a[4] a[5]
9
16
a[6]
a[7]
a[8]
a[9]
19
22
54
60
x=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
19
を探せ！
a[4] a[5]
9
16
a[6]
a[7]
a[8]
a[9]
19
22
54
60
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
x=
i=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
0
：左端
19
を探せ！
a[4] a[5]
9
16
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
i=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
0
を探せ！
19
x=
a[4] a[5]
9
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
16
：左端
k = (i+j)/2 =
4
：中央
※整数の演算なので
小数点以下切り捨て
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
を探せ！
19
x=
x > a[k] : 解は右にある！
i=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
0
a[4] a[5]
9
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
16
：左端
k = (i+j)/2 =
4
：中央
※整数の演算なので
小数点以下切り捨て
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
これより左に解はない：
探索しない
i=
x > a[k] : 解は右にある！
a[0]
a[1]
a[2]
a[3]
1
3
5
8
0
を探せ！
19
x=
a[4] a[5]
9
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
16
：左端
k = (i+j)/2 =
4
：中央
※整数の演算なので
小数点以下切り捨て
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
19
x=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
を探せ！
a[4] a[5]
9
16
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
右隣
k = (i+j)/2 =
4
i = k+1 =
5
：左端
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
を探せ！
19
x=
これより左に解はない：
探索しない
a[0]
a[1]
a[2]
a[3]
1
3
5
8
a[4] a[5]
9
i=
16
5
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
：左端
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
を探せ！
19
x=
これより左に解はない：
探索しない
a[0]
a[1]
a[2]
a[3]
1
3
5
8
a[4] a[5]
9
i=
16
5
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
：左端
k = (i+j)/2 =
7
：中央
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
を探せ！
19
x=
x < a[k] : 解は左にある！
a[0]
a[1]
a[2]
a[3]
1
3
5
8
a[4] a[5]
9
i=
16
5
a[6]
a[7]
a[8]
a[9]
19
22
54
60
j=
9
：左端
k = (i+j)/2 =
7
：中央
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
a[0]
a[1]
a[2]
a[3]
1
3
5
8
を探せ！
19
x=
a[4] a[5]
9
i=
16
5
これより右に解はない：
探索しない
a[6]
a[7]
a[8]
a[9]
19
22
54
60
：左端
7
k = (i+j)/2 =
左隣
j = j-1 =
6
：右端
：中央
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
を探せ！
19
x=
これより右に解はない：
探索しない
a[0]
a[1]
a[2]
a[3]
1
3
5
8
a[4] a[5]
9
i=
16
a[6]
a[7]
a[8]
a[9]
19
22
54
60
：左端
5
j=
6
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
a[0]
a[1]
a[2]
a[3]
1
3
5
8
を探せ！
19
x=
a[4] a[5]
9
i=
a[6]
a[7]
a[8]
a[9]
19
22
54
60
16
5
：左端
6
j=
k = (i+j)/2 =
5
：中央
※整数の演算なので
小数点以下切り捨て
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
を探せ！
19
x=
x > a[k] : 解は右にある！
a[0]
a[1]
a[2]
a[3]
a[4] a[5]
1
3
5
8
9
i=
a[6]
a[7]
a[8]
a[9]
19
22
54
60
16
5
：左端
6
j=
k = (i+j)/2 =
5
：中央
※整数の演算なので
小数点以下切り捨て
：右端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
x=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
を探せ！
19
a[4] a[5]
9
a[6]
a[7]
a[8]
a[9]
19
22
54
60
6
：右端
16
右隣
j=
k = (i+j)/2 =
5
：中央
※整数の演算なので
小数点以下切り捨て
i = i+1 =
6
：左端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
x=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
19
を探せ！
a[4] a[5]
9
a[6]
a[7]
a[8]
a[9]
19
22
54
60
6
：右端
16
j=
i=
6
：左端
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
x=
a[0]
a[1]
a[2]
a[3]
1
3
5
8
19
を探せ！
a[4] a[5]
9
a[6]
a[7]
a[8]
a[9]
19
22
54
60
6
：右端
16
j=
i=
k = (i+j)/2 =
6
6
：左端
：中央
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
x=
19
を探せ！
x == a[k] : ビンゴ！
a[0]
a[1]
a[2]
a[3]
1
3
5
8
a[4] a[5]
9
a[6]
a[7]
a[8]
a[9]
19
22
54
60
6
：右端
16
j=
i=
k = (i+j)/2 =
6
6
：左端
：中央
あらかじめ整列された配列の中から求める解があるかどうか探索する
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の候補
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の候補
解の候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の候補
解の候補
解の
候補
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の候補
解の候補
解の
候補
！
解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む
２分探索のイメージ：解の候補を片側「半分」に絞り込む
解
n件のデータ
解の候補
解の候補
解の候補
解の候補
解の
候補
！
O( log n ) （オーダろぐエヌ）のアルゴリズム：
n件のデータに対して、log n に比例する探索回数で済む→
nが1,000件に増えても、探索回数は10回程度
nが1,000,000,000,000件に増えても、探索回数は40回程度
log2 n

Download Report