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