2-6. 2分探索のアルゴリズムを擬似言語で記述する
本記事では、プログラムの説明及び擬似言語のプログラムを読んで、2次探索のアルゴリズムを記述する演習と解説を行います。
問題 次のプログラムの説明およびプログラムを読んで、設問に答えよ。
[プログラムの説明]
大きさn の配列Tの各要素 T[1], T[2], ‥, T[n] に異なる値が昇順に格納されている。与えられた変数data と同じ値が格納されている要素を、2分探索法で見つける。変数data の値と一致した要素が見つかると、その要素番号を変数idx に格納して検索を終了する。見つからなかったときは、変数idx を0とする。
2分探索法による検索の概要は、次のとおりである。
(1) 最初の探索範囲は、配列全体とする。
(2) 探索範囲の中央の位置にある配列要素の値（以後、中央の値と呼ぶ）と検索する値とを比較する。
(3) 比較の結果、
① 二つの値が等しければ、検索を終了する。
② "検索する値＞中央の値"であれば、検索する値は探索範囲の前半には存在しないので、後半を次の探索範囲とし、(2)に戻る。
③ "検索する値＜中央の値" であれば、検索する値は探索範囲の後半には存在しないので、前半を次の探索範囲とし、(2)に戻る。
④ 二つの値が一致せず、しかも探索範囲の要素が1個以上存在する値は、検索を継続する。
[プログラム]
idx ← 0
low ← 1
high ← □a
while (low ≦ high and idx = 0)
□ｂ
if (data = T[mid])
□c
elseif (data ＜ T[mid])
high ← mid - 1
else
low ← mid + 1
endif
endwhile
設問
プログラム中の□a、□b、□cに入れる正しい答えを、解答群の中から選べ。ただし、除算した結果の小数点以下は切り捨てとする。
□a に関する解答群
ア 0
イ 1
ウ n
エ n - 1
オ n + 1
カ n ÷ 2
□b、□cに関する解答群
ア high ← low × 2
イ idx ← high - low
ウ idx ← mid
エ low ← high - low
オ low ← high ÷ 2
カ mid ← (high - low) ÷ 2
キ mid ← (high + low ) ÷ 2
ク mid ← high -1
ケ mid ← low + 1
解答：(a) ウ、(b) キ、(c) ウ
解説
□a:
右端の初期値ですから、データ数である n になります。
□b:
中央の位置（mid）の計算をしていません。中央の位置は、（左端の位置 + 右端の位置）÷ 2 で求めるので、 mid ← (high + low ) ÷ 2 となります。
□c:
data = T[mid] ですから、見つかった時の内容です。見つかった時に変数idx にその要素番号を格納（mid）することは、問題文にも書いてありますから、idx ← mid となります。
Java版（二分探索）
public class BinarySearch {
public static int binarySearch(int[] T, int data) {
int low = 0; // 配列のインデックスは0から開始
int high = T.length - 1;
int idx = 0; // 見つからなかった場合の初期値
while (low <= high && idx == 0) {
int mid = (low + high) / 2;
if (T[mid] == data) {
idx = mid + 1; // 1-indexedの出力
} else if (data < T[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return idx; // 見つからなかった場合は0
}
public static void main(String[] args) {
int[] T = {1, 3, 5, 7, 9, 11, 13, 15}; // 昇順の配列
int data = 7; // 検索する値
int result = binarySearch(T, data);
System.out.println("検索結果: " + result);
}
}
Python版（二分探索）
def binary_search(T, data):
low = 0 # 配列のインデックスは0から開始
high = len(T) - 1
idx = 0 # 見つからなかった場合の初期値
while low <= high and idx == 0:
mid = (low + high) // 2
if T[mid] == data:
idx = mid + 1 # 1-indexedの出力
elif data < T[mid]:
high = mid - 1
else:
low = mid + 1
return idx # 見つからなかった場合は0
# 実行例
T = [1, 3, 5, 7, 9, 11, 13, 15] # 昇順の配列
data = 7 # 検索する値
result = binary_search(T, data)
print("検索結果:", result)
ポイント
1-indexed の結果を返すように idx = mid + 1 にしている。
配列は Java では 0 から n-1、Python でも 0 から n-1 なので low = 0、high = len(T) - 1 に設定。
mid = (low + high) / 2 の計算では整数除算（Java では / による整数演算、Python では // を使用）。
見つからなかった場合の idx = 0 の初期値はそのまま返す。
以上です。