サンプル問題科目B 問13 - 基本情報技術者試験問題を解いてみる

問13 次の記述中の [ ] に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。

関数 search は，引数 data で指定された配列に，引数 target で指定された値が含まれていればその要素番号を返し，含まれていなければ－1 を返す。data は昇順に整列されており，値に重複はない。

関数 search には不具合がある。例えば，data の [ ] 場合は，無限ループになる。

〔プログラム〕
○整数型: search(整数型の配列: data, 整数型: target)
整数型: low, high, middle

low ← 1
high ← dataの要素数

while (low ≦ high)
middle ← (low ＋ high) ÷ 2 の商
if (data[middle] ＜ target)
low ← middle
elseif (data[middle] ＞ target)
high ← middle
else
return middle
endif
endwhile

return －1

解答群
ア要素数が 1 で，target がその要素の値と等しい
イ要素数が 2 で，target が data の先頭要素の値と等しい
ウ要素数が 2 で，target が data の末尾要素の値と等しい
エ要素に－1 が含まれている

出典：基本情報技術者試験サンプル問題

問題を見て思うこと

このプログラムを見ると、これまでの業務の経験から、慎重に進める必要があると直感しました。配列でリングバッファを作るような場合とか、双方向リストを操作するような場合とか、今まで何度も失敗してきた経験があります（基本情報技術者試験では出ないのかも知れませんが）。この問題も、それに近いものを感じました。言わば、野生の勘です。

このプログラムで行いたいこと

このプログラムは、配列で二分探索を行おうとしています。つまり、配列の真ん中の値とtargetを比較して、targetが小さければ配列の前半に対して同じことを実行し、targetが大きければ配列の後半に対して同じことを実行する、ということを繰り返します。こうすることで、探索範囲がまず半分、さらにその半分、さらにその半分・・・と狭くなっていき、探索を効率よく行うことができるはずです。

なぜ無限ループになるのか

探索範囲がどんどん半分になれば、最終的に探索範囲が配列の要素1個になって、無限ループにならないように思います。そうならないということは、探索範囲を狭めるやり方に問題があるのかも知れません。

具体的に考えてみる

いつものように、具体例で考えてみます。次の図のように、dataが4つの要素からなり、その値は要素番号の2倍になっているものとします。ここで、target=8、つまり要素番号が最も大きい値を探します。

図に書き忘れましたが、変数lowの値を青色、変数highの値を赤っぽい色、変数middleの値を黄色で塗っています。配列dataの右側にあるlow, middle, highと書いて色が塗ってあるセルは、単に変数と色の関係を説明するものです。

1週目

まず、#1でlow（=1）とhigh（=4）を配列の両端に設定しています。

#3で配列の真ん中であるmiddle（=2.5の商で2）を計算します。

#4でtargetとの大小を判断して、targetは配列の真ん中の値より大きいので、#5でlowを配列の真ん中まで移動して、探索範囲を配列の後半にします。

2週目

#6から1週目と同じパターンで、#7でmiddle（=3）を計算して、targetは配列の真ん中の値より大きいので、1週目と同様にlowを配列の真ん中に移動します。

3週目（ここで無限ループ発生）

#10から3週目に入り、#11でmiddleを計算します。

ところが、low=3, high=4なので、middle=3になります。これは、#7と同じ計算結果です。

こうなると、計算を繰り返しても2週目と同じ結果になり、変数low, high, middleの値がどれも動かず、無限ループになります。

答えを考える

無限ループになるパターンが見つかったので、答えを考えてみます。最終的に、探索範囲の左端であるlow=3、探索範囲の右端であるhigh=4なので、配列の要素数は2と同じことです。targetはその2つの要素のうち、要素番号が大きい方（つまり末尾要素）と等しくなっています。この特徴にあう答えを解答群から探します。

ア要素数が 1 で，target がその要素の値と等しい

上で考えた条件とは、まず要素数が異なります。

要素数が1であれば、middleがその要素を指すので、targetと一致するかどうかすぐに判断でき、無限ループにはならないはずです。

こういうことから、この選択肢は違います。

イ要素数が 2 で，target が data の先頭要素の値と等しい

要素数が2というのは、上で考えた条件と一致します。

しかし上の例からわかるように、middleを計算すると配列の先頭要素を指します。すると、targetと一致するかどうかすぐに判断でき、無限ループにはならないはずです。

したがって、この選択肢は違います。

ウ要素数が 2 で，target が data の末尾要素の値と等しい

要素数が2で、targetが配列の末尾要素というのは、上で考えた条件と一致します。

ただし、よく考えてみると、targetとdataの末尾要素の値を比較しない（なぜならmiddleが末尾要素を指さないから）ので、targetがdataの末尾要素の値と等しくなくても無限ループになります。言い換えると、要素数が2で、targetがdataの先頭要素の値より大きい、というのが条件のように思います。

そんなこともありますが、この設問であれば、この選択肢が正しいです。