基本情報技術者試験

2分探索に関する記述のうち適切なものはどれか | 基本情報技術者試験過去問解説

プログラミング

こんにちは、フルスタックエンジニアのryuです。

今回の記事は、基本情報技術者試験過去問解説です。2分探索に関する問題についての解説をします。2分探索法とは、要素が昇順または降順に整列された集合に対して、探索範囲を1/2に狭めることを繰り返して目的のデータを探索するアルゴリズムです。今回の記事では、2分探索法のアルゴリズムについて詳しく解説します。

サーバー構築を実践で身につけるInfraAcademy

※本ページには、プロモーション・アフィリエイトリンクが含まれています

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です。

以上で解説を終わります。当ブログでは、このようなネットワークに関する内容や基本情報技術者試験の過去問解説をしているので興味のある方は引き続きご覧ください。

参考書を読む人
基本情報技術者試験過去問解説まとめ 午前問題過去問解説 基本情報技術者試験の過去問題を詳しく解説します。エンジニアの経験から実践を交えながら解説します! ...

ABOUT ME
ryu@InfraAcademyというインフラ学習サービス運営
大手企業→上場ベンチャー→スタートアップでエンジニアをしていました。 インフラエンジニア歴10年以上。 Linuxやネットワークの学習ができるサービスInfraAcademyを運営中。
RELATED POST