読み方のヒント

矢印ボタン(または ← → キー)でページを移動できます。

第2節 探索

2.2 2分探索

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[中]判定
11741212<15 なので 下 ← 5
25762020>15 なので 上 ← 5
355515一致。5を返す

3回の比較で見つかりました。

8 / 30