こんにちは、フルスタックエンジニアのryuです。
今回の記事は、基本情報技術者試験過去問解説です。2分探索に関する問題についての解説をします。2分探索法とは、要素が昇順または降順に整列された集合に対して、探索範囲を1／2に狭めることを繰り返して目的のデータを探索するアルゴリズムです。今回の記事では、2分探索法のアルゴリズムについて詳しく解説します。
2分探索に関する記述のうち適切なものはどれか
今回の記事では、以下の問題について解説します。
2分探索に関する記述のうち，適切なものはどれか。
ア:2分探索するデータ列は整列されている必要がある。
イ:2分探索は線形探索より常に速く探索できる
ウ:2分探索は探索をデータ列の先頭から開始する。
エ:n個のデータの探索に要する比較回数は，nlog2nに比例する。
出典：平成26年秋期 問6
答えは、『ア』の「2分探索するデータ列は整列されている必要がある。」です。
今回の記事では、2分探索法のアルゴリズムについて解説します。
2分探索法とは？
ここからは、2分探索法について解説します。
2分探索法とはデータを検索するためのアルゴリズム
2分探索法とは、データを検索するためのアルゴリズムです。Wikipediaには以下のように書かれています。
ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
引用:二分探索 – Wikipedia
良く分からないという方はこちらの動画が分かりやすいです！
2分探索法をPythonで実装する
では、2分探索法をPythonで実装してみましょう。コードは以下の通りです。まず、関数を定義します。
def binary_search(data, value):
left = 0 # 探索する範囲の左端を設定
right = len(data) - 1 # 探索する範囲の右端を設定
while left <= right:
mid = (left + right) // 2 # 探索する範囲の中央を計算
if data[mid] == value:
# 中央の値と一致した場合は位置を返す
return mid
elif data[mid] < value:
# 中央の値より大きい場合は探索範囲の左を変える
left = mid + 1
else:
# 中央の値より小さい場合は探索範囲の右を変える
right = mid - 1
return -1 # 見つからなかった場合
関数を定義したら、データを準備して、実行してみましょう。
data = [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(binary_search(data, 90))
→8 (90の場所)関数にデータと検索したい値を入力すると、配列の場所を返します。このように2分探索法をコーディングすることができます。
・参考:Pythonでアルゴリズムに入門する！ 押さえておきたい二分探索とバブルソートとは？
実装してみると、どのような動きをしているのか分るので試してみましょう！GoogleColaboratoryを使うとブラウザで実行することができます。以下のリンクからどうぞ。
Colaboratory へようこそ – Colaboratory (google.com)
アルゴリズムについては、こちらの参考書を読むと理解が深まります。
過去問解説まとめ
今回の記事では、以下の問題について解説します。
2分探索に関する記述のうち，適切なものはどれか。
ア:2分探索するデータ列は整列されている必要がある。
イ:2分探索は線形探索より常に速く探索できる
ウ:2分探索は探索をデータ列の先頭から開始する。
エ:n個のデータの探索に要する比較回数は，nlog2nに比例する。
出典：平成26年秋期 問6
答えは、『ア』です。その他の選択肢の解説についてはこちら。
- イ→目的のデータが先頭にある場合は、線形探索の方が早く検索できる
- ウ→2分探索は探索をデータ列の中央から開始する。
- エ→n個のデータの探索に要する比較回数はlog2nです。
以上で解説を終わります。当ブログでは、このようなネットワークに関する内容や基本情報技術者試験の過去問解説をしているので興味のある方は引き続きご覧ください。
