はじめに
この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の２２日目の記事です。
DNCLで二分探索を書いていきます。
二分探索とは
二分探索とは、昇順に並んだ配列の中から特定の値を高速に探すアルゴリズムです。
- 配列を半分に分け、中央の値と探している値を比較
- 値が中央より小さければ左半分、大きければ右半分を探索
これを繰り返して値を見つけます。
中央の値で探索範囲を半分にするのでO(logN)と、配列を前から順に見ていく線形探索よりも高速に探すことができます。
DNCLで二分探索を書く
配列Aからxを探します。
A ← {10, 23, 35, 47, 52, 68, 79, 81}
n ← 8
x ← 52
left ← 0
right ← n - 1
found ← 0
left <= rightの間、
| mid ← (left + right) ÷ 2
| もし A[mid] == x ならば
| | found ← 1
| | mid を表示
| | 繰り返しを抜ける
| を実行し、そうではなくもし A[mid] < x ならば
| | left ← mid + 1
| を実行し、そうでないならば
| | right ← mid - 1
| を実行する
を繰り返す
もし found == 0 なら
| 「値は見つかりませんでした」を表示する。
を実行する