読み方のヒント
矢印ボタン(または ← → キー)でページを移動できます。
2分探索は、昇順に整列された配列で使います。
○整数型: 二分探索(整数型の配列: data, 整数型: 目的)
整数型: 下, 上, 中
下 ← 1
上 ← dataの要素数
while (下 ≦ 上)
中 ← (下 + 上) ÷ 2 の商
if (data[中] = 目的)
return 中
elseif (data[中] < 目的)
下 ← 中 + 1
else
上 ← 中 - 1
endif
endwhile
return -1
data が {3, 7, 9, 12, 15, 20, 24}、目的が15のときのトレースです。
| 回 | 下 | 上 | 中 | data[中] | 判定 |
|---|---|---|---|---|---|
| 1 | 1 | 7 | 4 | 12 | 12<15 なので 下 ← 5 |
| 2 | 5 | 7 | 6 | 20 | 20>15 なので 上 ← 5 |
| 3 | 5 | 5 | 5 | 15 | 一致。5を返す |
3回の比較で見つかりました。
8 / 30