二分探索では、探す範囲の左端を low、右端を high、
中央の位置を mid として持ちます。
中央の値 a[mid] と探したい値 key を比較し、不要な半分を捨てます。
| 比較結果 | 次に探す範囲 | 更新 |
|---|---|---|
a[mid] = key | 見つかった | mid を返す |
a[mid] < key | 右半分だけ探す | low ← mid + 1 |
a[mid] > key | 左半分だけ探す | high ← mid - 1 |
div は整数除算を表します。
例えば 7 div 2 は 3 です。
○整数型: binary_search(整数型の配列: a, 整数型: key)
整数型: low, high, mid
low ← 1
high ← a の要素数
while ( low が high 以下 )
mid ← (low + high) div 2
if ( a[mid] が key と等しい )
return mid
elseif ( a[mid] が key より小さい )
low ← mid + 1
else
high ← mid - 1
endif
endwhile
return -1
low が high 以下 の間だけ繰り返す理由：low と high の間が、まだ探す候補が残っている範囲です。
low が high を超えたら、候補がなくなったので「見つからなかった」と判断します。
| 回数 | low | high | mid | a[mid] | 比較 | 次の動き |
|---|---|---|---|---|---|---|
| 1 | 1 | 7 | 4 | 17 | 17 < 21 | low ← 5 |
| 2 | 5 | 7 | 6 | 28 | 28 > 21 | high ← 5 |
| 3 | 5 | 5 | 5 | 21 | 21 = 21 | 5 を返す |
探したい値が配列に存在しない場合も、同じように範囲を半分ずつ狭めます。
最後に low が high を超えたら、探索範囲が空になったという意味です。
| 回数 | low | high | mid | a[mid] | 比較 | 次の動き |
|---|---|---|---|---|---|---|
| 1 | 1 | 7 | 4 | 17 | 17 > 10 | high ← 3 |
| 2 | 1 | 3 | 2 | 8 | 8 < 10 | low ← 3 |
| 3 | 3 | 3 | 3 | 12 | 12 > 10 | high ← 2 |
| 終了 | 3 | 2 | - | - | low > high | -1 を返す |
-1 を使います。
配列の要素番号は1から始まるため、-1 は実在する位置と混同しません。
| 項目 | 線形探索 | 二分探索 |
|---|---|---|
| 配列の条件 | 整列されていなくてもよい | 整列済みである必要がある |
| 調べ方 | 先頭から順番に調べる | 中央を見て半分ずつ範囲を捨てる |
| 最大比較回数の目安 | 要素数 n 回 | 約 log2 n 回 |
| 向いている場面 | 小さい配列、未整列のデータ | 大きく、整列済みのデータ |
mid の計算：(low + high) div 2 で中央を求める。a[mid] < key なら low ← mid + 1。a[mid] > key なら high ← mid - 1。low が high を超えたら見つからない。low ← mid や high ← mid にしない理由：
mid の位置はすでに調べ終わっています。
mid + 1 または mid - 1 にしないと、同じ位置を何度も調べて無限ループになることがあります。
二分探索を使うための前提条件として、最も適切なものはどれか。
要素番号が1から始まる配列で、low = 1、high = 9 のとき、mid ← (low + high) div 2 の結果はどれか。
(1 + 9) div 2 = 10 div 2 = 5 です。
div は整数除算なので、整数の位置を求めるときに使います。
次の二分探索のコードで、空欄 ［ A ］ に入る条件として適切なものはどれか。
low ← 1
high ← a の要素数
while ( ［ A ］ )
mid ← (low + high) div 2
...
endwhile
low から high までが探索範囲です。
low が high 以下なら、まだ調べる候補が残っています。
昇順に整列された配列で a[mid] が key より小さいとき、次に行う更新として正しいものはどれか。
elseif ( a[mid] が key より小さい )
［ B ］
endif
a[mid] より右側に、より大きな値があります。
a[mid] はすでに調べたので、次の探索範囲の左端は mid + 1 になります。
配列 {2, 5, 9, 13, 18, 21} から 13 を二分探索で探す。最初の比較で調べる値はどれか。要素番号は1から始まる。
low = 1、high = 6 なので、mid = (1 + 6) div 2 = 3。
最初に調べる値は a[3] = 9 です。
配列 {4, 7, 10, 15, 19, 23, 30} から 19 を二分探索で探す。次のトレースの空欄 ［ C ］ に入る値はどれか。
1回目: low = 1, high = 7, mid = 4, a[mid] = 15
15 < 19 なので low ← 5
2回目: low = 5, high = 7, mid = 6, a[mid] = 23
23 > 19 なので high ← 5
3回目: low = 5, high = 5, mid = 5, a[mid] = ［ C ］
19 です。
3回目で a[5] = key となるため、位置5を返します。
二分探索で、探す値が配列に存在しないと判断する状態として適切なものはどれか。
low から high までが探索範囲です。
low > high になると、探索範囲が空になったことを表します。
次の説明として正しいものはどれか。