質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • 基本情報技術者

    53questions

    基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。

【基本情報技術者】2分探索法

受付中

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 1,537

ai5

score 32

基本情報技術者試験

2分探索法
・データ領域の中央値で比較し、探索範囲を絞りこみ、目的のデータを探し出す。
・データは、昇順もしくは降順に整列されてなければならない。
・データがN件のとき、「き」は何回目で見つかるか?

1 2 3 4 5 6 7 8

【答え】3回目

公式ーーーーーーーーーーーーーーーーーーーーーー
平均比較回数:log2乗N回
最大比較回数:log2乗N+1回

2x≦N<2x+1
ーーーーーーーーーーーーーーーーーーーーーーーー

上記の公式をどう使えば答えの3回目が見つかるかよくわからないため、
ご教授ください。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • swordone

    2017/03/13 19:39

    log2_Nの2は、本来的logの右下に小さく表記されるものです。これは「2を何乗したらNになるか」ということを表し、その「何乗」がかかる数を底と呼びます。

    キャンセル

  • ai5

    2017/03/14 10:01

    そういうことだったんですね。ありがとうございます。

    キャンセル

  • 退会済みユーザー

    2017/03/14 10:05

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 4

+4

公式で求めることができるのはあくまで「平均比較回数」と「最大比較回数」です。
この問題の場合はデータと値および検索する値も提示されているので公式で求めることはできません。

・データがN件のとき、「き」は何回目で見つかるか?

これ問題そのままでしょうか?回答が出ないです。
「データーが8件の以下の場合」ではないでしょうか?

1 2 3 4 5 6 7 8

以下のとおり3回です

  1. 1~8の半分4の値より小さい
  2. 5(4+1)+8の半分6の値より小さい
  3. 7(6+1)+8の半分7の値と同じ

もし問題文が

・データが8件のとき、「き」は平均何回目で見つかるか?

なら公式平均比較回数log2Nを使用してN=8なのでlog2 8=3と求まります。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

1〜8にデータがあり、N=8です。
探したい対象はきで、s="き"とします。

1

二分探索は、まず名前の通りデータを二分します。
範囲は1〜8なので
(1+8)/2 = 4 ※切り捨て

データから、4番目の"え"と"き"を比較すると、"き"のほうが大きいです。

つまり、sはデータの5〜8にあることがわかります。

2

更に範囲内の中央を取るために平均を取ります。
(8+5)/2 = 6

6番目の"か"と"き"を比較すると、"き"のほうが大きいです。

sはデータの7〜8にあることがわかります。

3

同様に
(7+8)/2 = 7

7番目の"き"と"き"を比較すると、等しいです。
sはデータの7番。探索終了です。


  • なぜ、データがより上(または下)にあることがひとつのデータをみただけでわかるのか?
    二分探索はデータが整列済みであることを前提としているからです。

  • 公式は使わないのか?
    例えば"き"を探すときは最大でも平均でもない比較回数(1回)になります。
    回数が最大か平均かを判断できない場合は公式は無意味です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/13 17:35

    お返事遅くなり申し訳ありません。

    ものすごくわかりやすい解説かと存じますが、私の理解が追い付いてないです。。。
    以下質問です。

    1
    二分探索は、まず名前の通りデータを二分します。
    範囲は1〜8なので
    (1+8)/2 = 4 ※切り捨て
    →データは8個しかないのになんで1+8なんですか?
    また、なんで切り捨てするのでしょうか?

    データから、4番目の"え"と"き"を比較すると、"き"のほうが大きいです。

    つまり、sはデータの5〜8にあることがわかります。

    2

    更に範囲内の中央を取るために平均を取ります。
    (8+5)/2 = 6

    2では更に範囲内の中央を取るために平均を取ります。と書いてあるのですが、
    1の計算は平均を取ってるものではなかったのですか?



    キャンセル

  • 2017/03/13 19:27

    横から失礼。
    1.要は、「真ん中」を知りたいのです。1〜8の真ん中は、並べてみると
    12345678
    の真ん中ですから、4と5の間になります。これを数値的に、(1+8)/2としています。
    この答えは4.5と出ますが、配列の番号として使う以上、整数にする必要があります。切り上げでも切り捨てでもいいのですが、一般的にコンピュータでの整数の除算は余り切り捨てで出るため、切り捨てを採用しています。
    2.これも、5〜8の「真ん中」を知りたいのです。説明は同じなので省略。

    キャンセル

  • 2017/03/13 23:10

    swordoneさん的確な回答ありがとうございます
    >1の計算は平均を取ってるものではなかったのですか?
    平均を取ってます。公式にするなら、
    (範囲の下限+範囲の上限)/2
    で平均が取れます。最初は1~8なので、これを代入して
    (1+8)/2
    としたわけです。
    8/2でもいいですが、それをすると2回目以降で同じ公式が使えなくなるので避けました。

    キャンセル

  • 2017/03/14 01:15

    最近調べてて知ったのですが、この「足して2で割る」という方法は間違った方法(数値が大きいとオーバーフローを起こす)で、一時期多くの実装で間違っていたそうです。Javaでは1998~2006まで間違っていたとのこと(Wikipedia-二分探索より)。
    正しい実装はこの例でいうと1+(8-1)/2とのこと。「最小値に区間の半分を足す」という方法ですね。

    キャンセル

  • 2017/03/14 03:06

    left+(right-left)/2
    ってことですかね
    文章題ではオーバーフローは起きえないので本題とはずれている気もしますが、勉強になります。

    キャンセル

  • 2017/03/14 09:56

    皆様理解が進みました。ありがとうございました。

    キャンセル

+1

なぜかと言われれば、二分木探索とは、1回の探索で範囲を半分に絞り込むからです。
元のデータ個数が N として、探索回数が
1回: N/2
2回: N/4 (N/2 /2)
3回: N/8 (N/2 /2 /2)

n回: N/(2^n)
となりますから、最悪でも 2^n >= N となる n までの回数で探索が完了(対象個数が1以下になる)します。これを数学的に表現すると、log2N となります。
今回の場合、N=8 ですから、 log2 * 8 = 0.301 *8 = 2.408 なので、切り上げて 3 が答えです。
※平均試行回数でいうと切り上げずに 2.4 回がそのまま解になります

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/04 10:08

    log2Nの2は対数の底なのに、いつの間にか常用対数の真数になってる…

    キャンセル

0

回答としてはこちらのホームページをご覧ください

https://oshiete.goo.ne.jp/qa/3092132.html

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • 基本情報技術者

    53questions

    基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。