下記写真はアルゴリズムの問題なのですが、なぜ(2)

質問

下記写真はアルゴリズムの問題なのですが、なぜ(2)がmid +1でなく、(3)がmid-1でないのか分かりません。教えて頂きたいです。よろしくお願い致します。

回答No.1

asciiz · ベストアンサー

いやちょっとこれ、5分じゃとても考えきらなかったんですけども!?
一応、「low=mid・high=mid」ペアでないと困る理由は見つかりました。
※整数の割り算において、小数点以下は切り捨てるものとします(例: 7÷2=3 )

--

TBL[1]=1, TBL[2]=2, …というデータがあったとします
要素数N=4の場合を考えてみます

ループ条件の方、(high - low)>1 は問題ないですね。
ではここで、low=mid+1・high=mid-1 と置いたときに、データ「0」を探索してみます。

ループ突入時 low=0, high=5, mid=2
1ループ目 TBL[2]は0より大きい high=1になる→mid=0になる
ループ条件に外れるので脱出
TBL[0] は範囲外の添字となり、実行時エラーが生じてしまう。※これはまずい!!

従って、『この問題においては』、エラーの可能性をなくすために low=mid・high=mid ペアでないといけません。
探索範囲の狭まり方がループごとに1ずつ大きいですが、エラーを避けるためには仕方ありません。

…と言うことだと思いました。

--

でもそれってそもそもが、low=0・high=N+1で初期化してるからまずいんですよね?
low=1、high=N で初期化した時に、low=mid+1・high=mid-1 ペアならば?

要素数N=4の時に、データ「0」を探索してみます。

ループ突入時 low=1, high=4, mid=2
1ループ目 TBL[2]は0より大きい high=1になる→mid=1になる
ループ条件に外れるので脱出
TBL[1]は0ではないので、「見つからなかった」という表示でOK。

今度は大丈夫そうです。
でも別のデータでもう1回。

要素数N=4の時に、データ「4」を探索してみます。

ループ突入時 low=1, high=4, mid=2
1ループ目 TBL[2]は4より小さい low=3になる→mid=3になる
ループ条件に外れるので脱出
TBL[3]は4ではないので、「見つからなかった」という間違った表示をしてしまう。

いやこれはループ条件が悪いのでは? (high-low)>0 という条件にしてみます。

ループ突入時 low=1, high=4, mid=2
1ループ目 TBL[2]は4より小さい low=3になる→mid=3になる
2ループ目 TBL[3]は4より小さい low=4になる→mid=4になる
ループ条件に外れるので脱出
TBL[4]は4なので、「見つかった」という表示でOK。

最終プログラムをまとめるとこうなります。

low ← 1
high ← N
mid ← (low + high)÷2
■(high-low) > 0 and TBL[mid]≠DATA
｜ IF TBL[mid] < DATA
｜ THEN low ← mid + 1
｜ ELSE high← mid - 1
｜
｜ mid ← (low + high)÷2
■
IF TBL[mid] = DATA
THEN "一致データあり" を表示
ELSE "一致データなし" を表示

--

そうすると、問題文通りの組み方と、改良を加えていった最後の組み方、2通りの組み方ができて、どちらも正しいと思います。

でも、問題文の初期化部分はいじれないので、この問題においては「ア」のみが正答と言うことになってしまいますね。

+1・-1 が気になったことについて、プログラミングセンスがあると思います。
あと条件判定において、0を含める/含めない、「以上」「以下」と「より大きい」「より小さい」なんてのも、その境界状態でどっちに判別するかが重要になってくることがよくあります。
がんばってください。

お礼

貴重お時間頂いてありがとうございました。
頑張ります！