2-5. 2分探索法による探索処理
本記事では、２分探索法による探索処理のアルゴリズムについて解説します。問題のレベルは、基本情報技術者試験レベルです。
問題 昇順に整列されたn個のデータが格納されている配列Aがある。流れ図は、2分探索法を用いて配列Aからデータxを探し出す処理を表している。□a, □b に入る操作の正しい組合せはどれか。ここで、除算の結果は小数点以下が切り捨てられる。
選択肢
ア □a: hi ← k + 1、□b: lo ← k - 1
イ □a: hi ← k - 1、□b: lo ← k + 1
ウ □a: lo ← k + 1、□b: hi ← k - 1
エ □a: lo ← k - 1、□b: hi ← k + 1
解答：ウ
解説
解説の前に
流れ図中の「：」の意味
この記号は「比較演算（関係演算）」を表しています。
「A[k] : x」の意味
これは「A[k] と x を比較する」という処理を示しており、その後に分岐があることから、「A[k] と x を比較して、=・>・< のいずれかの条件に応じた処理に進む」 という意味になります。
この問題は「二分探索法（バイナリサーチ）」を流れ図で表したものであり、与えられた選択肢の中から正しい操作（□a, □b に入る処理）を選ぶものです。
まず、流れ図の処理の流れを確認し、その後に□a, □b の適切な操作を選定します。
loは下限、lhは上限を示します。kは、配列の中央位置のデータを示します。
中央値から後半の範囲の始まり（下限）は、 k+1と表現します。
中央値から前半の範囲の終わり（上限）は、k-1と表現します。
1. 二分探索法の基本
二分探索法（バイナリサーチ）は、ソートされた配列に対してデータを効率的に探索するアルゴリズムです。
探索範囲の初期化
lo = 1（配列の最初のインデックス）
hi = n（配列の最後のインデックス）
中央の要素を確認
k = (lo + hi) / 2（中央のインデックスを求める、小数点以下切り捨て）
A[k] を x（探したい値）と比較
比較の結果に応じて探索範囲を変更
A[k] == x の場合 → 探索成功（x は配列内に存在）
A[k] > x の場合 → x は A[k] より左側にあるため、高い方の範囲を狭める（hi = k - 1）
A[k] < x の場合 → x は A[k] より右側にあるため、低い方の範囲を狭める（lo = k + 1）
範囲が lo > hi になった場合、探索失敗（x は存在しない）
2. 流れ図の解析
流れ図の各部分を見ていきます。
初期化（lo = 1, hi = n）
→ 配列全体を探索範囲として設定中央の要素 A[k] を決定
→ k = (lo + hi) / 2A[k] と x の比較
等しい (A[k] == x) → 「x は存在する」と判定し、終了
A[k] > x の場合 → x は A[k] より左側にあるため、探索範囲の上限を更新（hi = k - 1）
A[k] < x の場合 → x は A[k] より右側にあるため、探索範囲の下限を更新（lo = k + 1）
探索範囲の判定 (lo <= hi)
満たす場合 → 再度 k を更新し、ループを続ける
満たさない (lo > hi) → x は存在しないと判定し、終了
3. □a, □b に入る処理の決定
流れ図の構造から
A[k] > x の場合（x は左側にある）
→ 探索範囲の上限を狭める（hi = k - 1） → □b に入る処理A[k] < x の場合（x は右側にある）
→ 探索範囲の下限を狭める（lo = k + 1） → □a に入る処理
したがって、
□a = lo = k + 1
□b = hi = k - 1
となり、これは 選択肢「ウ」 に該当します。
4. 最終確認
選択肢 ウ
□a: lo ← k + 1
□b: hi ← k - 1
この動作は二分探索のルールに合致しており、正しい解答です。
よって、正解は「ウ」です。
補足1
本問題（二分探索法）のコードを Java と Python で実装
流れ図を元に、Java と Python の両方でコーディングします。
基本的な仕様
配列 A は 昇順にソート済み とする。
探索する値 x を入力し、配列内に存在するかどうかを判定する。
存在する場合は「x は存在する」
存在しない場合は「x は存在しない」
✅ Java 実装
import java.util.Scanner;
public class BinarySearch {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 昇順にソートされた配列
int[] A = {1, 3, 5, 7, 9, 11, 15, 18, 21, 25};
int n = A.length;
// 探索する値を入力
System.out.print("検索する値 x を入力してください: ");
int x = scanner.nextInt();
// 二分探索を実行
boolean found = binarySearch(A, n, x);
// 結果を表示
if (found) {
System.out.println(x + " は存在する");
} else {
System.out.println(x + " は存在しない");
}
scanner.close();
}
public static boolean binarySearch(int[] A, int n, int x) {
int lo = 0;
int hi = n - 1;
while (lo <= hi) {
int k = (lo + hi) / 2; // 中央のインデックス
if (A[k] == x) {
return true; // x を発見
} else if (A[k] > x) {
hi = k - 1; // 左側を探索
} else {
lo = k + 1; // 右側を探索
}
}
return false; // 見つからなかった場合
}
}
📌 Java のポイント
binarySearch メソッド で二分探索を実装。
while (lo <= hi) の条件で探索を繰り返す。
A[k] == x の場合は true を返して終了。
A[k] > x なら hi = k - 1（左側を探索）。
A[k] < x なら lo = k + 1（右側を探索）。
lo > hi になった場合は false（x は存在しない）。
✅ Python 実装
def binary_search(A, x):
lo = 0
hi = len(A) - 1
while lo <= hi:
k = (lo + hi) // 2 # 中央のインデックス（整数除算）
if A[k] == x:
return True # x は存在する
elif A[k] > x:
hi = k - 1 # 左側を探索
else:
lo = k + 1 # 右側を探索
return False # x は存在しない
# 昇順にソートされた配列
A = [1, 3, 5, 7, 9, 11, 15, 18, 21, 25]
# ユーザーから入力を受け取る
x = int(input("検索する値 x を入力してください: "))
# 二分探索の実行
if binary_search(A, x):
print(f"{x} は存在する")
else:
print(f"{x} は存在しない")
📌 Python のポイント
binary_search 関数で二分探索を実装。
// を使って 小数点以下を切り捨てる（(lo + hi) // 2）。
リスト A の長さ len(A) - 1 を hi の初期値に設定。
while lo <= hi の間、探索を繰り返す。
🔍 Java & Python 共通の動作
検索値 x 配列 A に含まれるか 出力結果 7 ✅ 含まれる 7 は存在する 12 ❌ 含まれない 12 は存在しない
💡 まとめ
Java / Python の両方で、基本的な二分探索の流れは共通。
中央の値 A[k] を x と比較し、探索範囲を絞る のがポイント。
時間計算量は O(log n) で高速（配列サイズ n に対し、最大 log_2(n) 回の比較で済む）。
以上です。