基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

平成20年秋期 午前問13について疑問がございます。

設問の最後に「該当するキーが必ず表中にあることが分かっているとき，キーの比較回数は最大何回か。」と記載がありますが、該当するキーが必ず表中にあることが分かっているのであれば最後の比較は行う必要が無く、比較回数は10回になると思うのですがいかがでしょうか。

最後の比較とは、探索対象の要素が残り1個になった場合、それが該当キーと一致するかどうかを確認するための比較のことですかね。

例  (2,4,7,9,11)の中から"4"を探す

①"7"と"4"を比較→7＞4なので、7以上の要素を除外  残りの要素  (2,4)
②"2"と"4"を比較→2＜4なので、2以下の要素を除外  残りの要素  (4)
③"4"と"4"を比較→一致  該当する要素を発見

該当するキーが必ず表中にあることが分かっているのであれば、③の比較は不要（残りの要素が1個になった時点でその要素が該当することが確定するから）という意味であれば、あなたが正しいです。

>最後の比較とは、探索対象の要素が残り1個になった場合、それが該当キーと一致するかどうかを確認するための比較のことですかね。
はい、おっしゃる通りです。
ご丁寧にありがとうございます。

で、あるならば公式の回答が間違っている（公式はウの11回）という認識でよろしいでしょうか。

TKさん

横から失礼します。

最後の比較(要素数が1になったときの比較)を行わないとすると、最大比較回数が10回となる理由を説明していただけないでしょうか。

IPAは正解のみで解説を出していませんし、このサイトの解説でも最後の比較を行う前提となっているように読めませんでした。

この問題は、アルゴリズムの問題で人間の思考の問題ではないと思います。
例えば、（1,2,3,4,5,6,7)という表で考えてみます。
探索キーが、２の場合  中央値４と比較  より小さいので  (1,2,3)が残ります。
次に、中央値２と比較  同じなので探索終了。比較２回

探索キーが、４の場合  中央値４と比較  同じなので探索終了。比較１回

探索キーが、３の場合  中央値４と比較  より小さいので  (1,2,3)が残ります。
次に、中央値２と比較  より大きいので  (3)が残ります。
人間ならば、ここで終了できますが、アルゴリズムなので次に進みます。
探索キーと中央値の３を比較  同じなので探索終了。比較は３回となります。

処理を終了するには、同じになったときに探索を終了するという条件分岐が必要になります。
そう考えると、問題文中の”該当するキーが必ず表中にあることが分かっている”は、無限ループにならないための条件のような気がします。

>dさん
2,000個のデータ列に対して2分探索を行うとすると、
1回目の比較を2000個のデータに対し実施すると、次の検索範囲は999個か1000個になります。
最大比較回数なので探索範囲が多いほうを選択します。（どちらでも大きな影響は無いと思いますが）
ですので、
2回目の比較を1000個のデータに対し実施すると、次の検索範囲は499個か500個になります。
3回目の比較を500個のデータに対し実施すると、次の検索範囲は249個か250個になります。
4回目の比較を250個のデータに対し実施すると、次の検索範囲は124個か125個になります。
5回目の比較を125個のデータに対し実施すると、次の検索範囲は62個になります。
6回目の比較を62個のデータに対し実施すると、次の検索範囲は30個か31個になります。
7回目の比較を31個のデータに対し実施すると、次の検索範囲は15個になります。
8回目の比較を15個のデータに対し実施すると、次の検索範囲は7個になります。
9回目の比較を7個のデータに対し実施すると、次の検索範囲は3個になります。
10回目の比較を3個のデータに対し実施すると、次の検索範囲は1個になります。
そして問題の11回目ですが、該当するキーが必ず表中にあることが分かっていないのであれば、最後の1個と入力したキーを比較する必要がありますが、問題文に記載があるように分かっているのであれば、最後は比較する必要がなく入力したキーと一致することがわかると思います。
ですので今回のように問題文に「該当するキーが必ず表中にあることが分かっているとき」という但し書きがあるのであれば比較回数は公式通りではなく公式で出た値-1になると考えられると思います。

こちらでよろしいでしょうか。
まだ、もしくは他に疑問点がございましたらお手数ですが投稿お願いいたします。

>boyonboyonさん
>この問題は、アルゴリズムの問題で人間の思考の問題ではないと思います。
その通りだと思いますが、探索するキーが表中（探索範囲）にあると事前に分かっている場合と分かっていない場合で使うアルゴリズムが異なるのではないかと思います。

ざっくり記載いたします
分かっていない場合・・・最後の１個と入力したキーの比較が必要
分かっている場合・・・最後の１個になった時点で入力したキーと一致する比較が不要なので、比較作業を行わずにループを抜ける

>処理を終了するには、同じになったときに探索を終了するという条件分岐が必要になります。
そう考えると、問題文中の”該当するキーが必ず表中にあることが分かっている”は、無限ループにならないための条件のような気がします。
仰る様に無限ループを防ぐために記載しているのかもしれませんが、その結果比較回数に影響が出てしまい、公式の回答が誤っていると考えました。

TKさん

ご説明ありがとうございます。

>最大比較回数なので探索範囲が多いほうを選択します。
この点については私もその通りだと思います。

>1回目の比較を2000個のデータに対し実施すると、次の範囲は999個か1000個になります。
疑問なのですが、もしかしてここで999個、1個、1000個の3つに分けていないでしょうか？
その場合、2回比較を行っていることになります。
(例えば、if 1000番目の要素と等しい elseif 1000番目の要素より大きい else …)

探索範囲の要素数が偶数の場合は、2等分(上の例ですと、2つの1000個)します。
探索範囲の要素数が奇数(2k + 1, kは正の整数)の場合は、kとk + 1の2つに分けます。
この方法で最大比較回数を求めてみますが、続けると長くなりますので次の投稿で。

比較回数    比較後の探索範囲要素数
0回目      2000
1回目   1000
2回目   500
3回目   250
4回目      125
5回目   63
6回目   32
7回目   16
8回目   8
9回目   4
10回目   2
11回目   1

となりました。

＞TKさん

午後試験を来週に控えているので、こちらのスレッドで話題にしていることはアルゴリズムについて良い勉強になっています。良いテーマを提供していただいてありがとうございます。もし、二分探索の問題が出題されたらにやけてしまいそうです。
前回の投稿について一つ訂正です。無限ループ．．．と書きましたが、そうならないように作れることが調べたら分かりました。

勉強したことを自分なりに整理して下記の疑似アルゴリズムを作ってみました。
読んでいただけたら幸いです、
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
前提条件：該当するキーが必ず表中にあることが分かっている

要素数  N
要素列中  K  番目の要素  要素（K）  

初期値  左端＝１、右端＝N
探索するキー  X
とします。

繰り返し（左端＜＝右端）
中央位置←（左端＋右端）÷２の商
        比較処理
                X>要素（中央位置）
左端←中央位置＋１
X<要素（中央位置）
右端←中央位置－１
X=要素（中央位置）
探索終了
比較処理終了

＊＊＊＊＊＊＊＊＊＊  

繰り返しに戻る
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
これですと、最後に１つ残ったときに比較してしまいますが、

繰り返し（左端＜＝右端）の＝を外し、
＊＊＊＊＊＊＊＊＊＊の箇所に
“左端＝右端ならば探索終了”という処理を付け加えると
おっしゃるとおり比較回数は、１回少なくなると思います。
このような理解でよろしいでしょうか。

残る問題は、“左端＝右端ならば探索終了”を入れた方が良いのか、
それとも入れない方が良いのかということですね。

補足  該当するキーが存在しないと繰り返しループを抜けてしまいます。
なので、“繰り返しにもどる“の次は、

該当するキーなしで処理終了

となります。

すみません、疑似アルゴリズムのインデントがへんになってしまいました。
訂正して、再掲します。

繰り返し（左端＜＝右端）
        中央位置←（左端＋右端）÷２の商
        比較処理
                X>要素（中央位置）
                        左端←中央位置＋１
                X<要素（中央位置）
                        右端←中央位置－１
                X=要素（中央位置）
                        探索終了
        比較処理終了

＊＊＊＊＊＊＊＊＊＊  

繰り返しに戻る

boyonboyonさん

>この問題は、アルゴリズムの問題で人間の思考の問題ではないと思います。
どちらでも解く事は可能ですが、アルゴリズムのトレースをせずに解いた方が簡単だと思います。
トレースせずに解く方法はこのサイトの解説にあります。

アルゴリズムをトレースする場合は、中央位置の要素が探索値と等しいか、探索値より小さいか、探索値より大きいか、という3つに分ける方法を回避する必要があります。

>dさん(No.8) 
>疑問なのですが、もしかしてここで999個、1個、1000個の3つに分けていないでしょうか？
>その場合、2回比較を行っていることになります。
すみません。私の記載が悪かったですね。これは3つに分けるわけではありません。
例えば1～2000までの要素を2分探索すると始めは中央値の1000(999でも1001でもいいと思います）と入力キーを比較します。すると次の2回目の比較は1000は既に比較しているので比較不要。残った要素は999個と1000個に分けられます。
今回の問題ですと最大比較回数なので多い方の要素を次に比較対象の要素にするという考えになるかと思います。

>dさん(No.9) 
>比較回数    比較後の探索範囲要素数
>4回目      125
>5回目   63
上記の数が要素数を表しているのであれば2分探索では上記のようにはならないと思います。
4回目の比較で1～125の中央値の63と比較します（要素数なので1～125とは限りませんが、わかりやすい？例として記載します）ので次の5回目の比較では63の比較は不要。ですので次の要素数は62個になります。
同様に比較していくと10回目の比較で要素数は1個になると考えられます。

>dさん(No.12) 
すいません横から失礼いたします。

>どちらでも解く事は可能ですが、アルゴリズムのトレースをせずに解いた方が簡単だと思います。
>トレースせずに解く方法はこのサイトの解説にあります。
確かにその通りなのですが今回の問題ですと、公式に代入して解いた場合（トレースを使用しない）と問題に沿ったアルゴリズムを考え解いた場合（トレースする）で異なる回答が出てしまうのが問題なのかなと思います。
（多分dさんはこういう解き方もありますよ、という親切心で記載したと思いますが、本スレの論点がずれてしまいそうだと思ったので勝手に横やり入れてしまいました。。。申し訳ございません。）

>boyonboyonさん(No.10) 
>“左端＝右端ならば探索終了”という処理を付け加えると
>おっしゃるとおり比較回数は、１回少なくなると思います。
>このような理解でよろしいでしょうか。
はい、その認識で問題ありません。

>残る問題は、“左端＝右端ならば探索終了”を入れた方が良いのか、
>それとも入れない方が良いのかということですね。
はい、このスレッドでは上記の内容を論点にしているつもりです。（入れる場合と入れない場合で比較回数、つまり回答が異なってしまうと考えるため）

非常にわかりやすいアルゴリズム（プログラム）まで考えていただいてありがとうございます。
午後試験頑張ってください。
このスレッドが多少なりとも役に立ったのであれば幸いです。

TKさん

>>dさん(No.9) 
>>比較回数    比較後の探索範囲要素数
>>4回目      125
>>5回目   63
>上記の数が要素数を表しているのであれば2分探索では上記のようにはならないと思います。
改めて考えてみたのですが、ご指摘の通り上記のようにはなりませんでした。

>探索範囲の要素数が奇数(2k + 1, kは正の整数)の場合は、kとk + 1の2つに分けます。
投稿No.8で私がこのように投稿し、投稿No.9ではk + 1を次の探索範囲とする前提で計算していました。しかし、それは誤りで次の探索範囲はkになり、この計算結果は投稿No.6のTKさんの結果と一致しました。勉強になりました。

>dさん(No.17) 

私の投稿検証していただきありがとうございました。
また何か不明点や疑問点が御座いましたら投稿よろしくお願いいたします。

＞TKさん(No.16)
励ましの言葉ありがとうございます。
本日、午後試験受けてきました。結果の報告は、別スレをたてます。

>boyonboyonさん(No.19) 
おめでとうございます！！

該当のスレッドにも記載させていただきましたが、改めて！