二分探索アルゴリズムの終了条件について

質問

いつもお世話になっています。

現在他人のプログラムを読解する力をつけようと
訓練しています。

以下の文はとあるアルゴリズム本の２分探索の個所を
抜粋したものです。

int bs(*array, size, mokuteki)
{
　　ue=size-1, sita=0;

　　while(1){
　　　　naka=(sita+ue) / 2;
　　　　if(array[naka] == mokuteki)
　　　　　　return ARU;
　　　　else if(sita > ue) //・・・・・・★
　　　　　　return NAI;
　　　　else {
　　　　　　if(array[naka] < mokuteki)
　　　　　　　　sita = naka+1;
　　　　　　else
　　　　　　　　ue = naka-1;
　　　　}
　　}
}

ここで★部分の終了条件なのですが、なぜ
　　sita >= ue
でいけないのか自分では理解できません。

要はsitaとueが同じ値になり、目的値が見つからなかった
のに再度ループする必要があるのか？、ということです。

特に明確な答えはいりませんがぜひ
ご意見を聞かせてください。

ちなみに作者は
「ue==sitaの状態ならば、幅１の範囲がありますから
　ループをもう一回実行する必要があります。」
と書いています。私には理解できません。

ちなみにこの本は「Javaで学ぶアルゴリズムとデータ構造」
という本です。だいたい一通り読みましたが読んでて
楽しいしわかりやすいし良書だと思います。高価ですが・・・。

回答No.5

noname#30727 · ベストアンサー

再度ループさせる必要な無いしょう。
size が 0 であるリストを探索することもありますから、どちらにしても、先にarray[naka]を判定をするのは良くないです。

少し飛躍しますが、見つからなかった時にリストに追加しなければならない場合がありますよね？
soakunさんの例だと、ループを抜けた後に、l がそのまま挿入インデックスになるので都合がいいです。

個人的な趣味だと、break しているところは、return が好きなんですけど。

お礼

待ちに待った「自身あり」の肯定意見をありがとうございます。

さらにアルゴリズムの間違いまで指摘してくれてとても助かりました。

＞size が 0 であるリストを探索することもありますから、

ごもっともです。もしそんなことしてたら
割り当てられてない記憶領域へアクセスさせて
クラッシュしてしまう所でした。

すばらしすぎます。どうやったらそこまで
見抜く力が付くのでしょうか？

回答No.4

soakun

あう、そのとおりです(たはは～(汗
ご指摘どおり、不等号が逆転してますです；

お礼

自身満々で書いた場所の誤りは非常に見つけづらいと思います。
そんなsoakunさんのこれからの活躍を祈ってにポイントを
差し上げたいと思います。
えっ、えらそうですって。ごめんなさいです。

私のこんなひねくれた質問を読んで考えてくださった
方々全員に感謝いたします。

回答No.3

soakun

>ところでsoakunさんのプログラムに誤りらしきものが・・(^^;

あぅ、どこが間違いなのでしょう？(^^;
# もしかしたらここを見る人のためにも修正したいので補足よろしゅー

補足

はい。入力ミスっぽいのとうっかりミスっぽいのがありました。

（１）while(l > h)
　　　これの符号は逆ですよね。

（２）while(・・){
　　　　if(array[t] == mokuteki)
　　　　　　break;
　　　｝
　　　return (l > h) ? t : (-1);

　　　目的値が見つかっても負を返しちゃいますよね。　　　

間違ってたらごめんなさいです。(~~)/~

回答No.2

soakun

二分木探索について手元にあるアルゴリズム書から
Cに書きおこしたものを書いてみます。
# この段階で上のプログラムと若干異なっているのですが(^^;

int
bs(array, size, mokuteki)
int *array;
int size;
int mokuteki;
{
int l = 0;
int h = size - 1;
int t;

while(l > h) {
t = (l + h) / 2;
if(array[t] == mokuteki)
break;
else if(array[t] < mokuteki)
l = t + 1;
else /* if(array[t] > mokuteki) */
h = t - 1;
}
return (l > h) ? t : (-1);
}
ここで、配列の値を、

int array[] = { 2, 4, 6, 9, 10, 15, 17, 18, 20 };

とし、
int mokuteki = 29;

でプログラムを実行させてみてください。
上記の関数は目的とする配列の添字が見つからなければ、
負の数を返します。
/* おまけ(Javaで書いた場合) */
class BinarySearchTest {
public static int search(Object ref, int mokuteki) {
int[] array = (int[])ref;
int l = 0;
int h = array.length - 1;
int t = -1; /* dummy */

while(l > h) {
t = (l + h) / 2;
if(array[t] == mokuteki)
break;
else if(array[t] < mokuteki)
l = t + 1;
else /* if(array[t] > mokuteki) */
h = t - 1;
}
return (l > h) ? t : (-1);
}

public static void main(String[] args) {
int array[] = new int[] { 2, 4, 6, 9, 10, 15, 17, 18, 20 };
int mokuteki = 29;

System.out.println("index:");
System.out.println(search(array,mokuteki));
System.out.println("\n");
}
}

お礼

プログラムまで書いていただきまことにありがとうございます。

う～ん。やはり目的値が見つからなかった場合の
終了判定はwhileループの外でした方が明確になりますね。

ところでsoakunさんのプログラムに誤りらしきものが・・(^^;

もうそろそろ私も
「作者がまちがいだ！」という風に妥協し始めてます。

「うん、そうだね。」とうなずいていただけると嬉しいのですが・・・

回答No.1

yusuke5111

sitaとueが同じ値になり、目的値が見つからなかったのに再度ループする必要はないと思いますが、
以前に、同じようなプログラムを書いたとき、sita >= ue では正しく動かなかったような記憶があります。

補足

ご意見たいへんありがとうございます。

動作を確認できそうなプログラムを作成してみました。
Ｃですみません。

★の部分を
　　sita >= ue
に変更してもうまくいってしまいます。
どなたか失敗する例を知らないでしょうか？

#include <stdio.h>

enum{ NAI, ARU };
int bs(int array[], int size, int mokuteki);

int main(void)
{
　　int array[]={1,3,6,13,14,19,19,22,30};
　　int i,size;
　　size=sizeof(array) / sizeof(array[0]) ;

　　for(i=0; i<30; i++){
　　　　int ret;
　　　　ret=bs(array, size, i);

　　　　if(ret == ARU)
　　　　　　printf("%d:ある",i);
　　　　else
　　　　　　printf("%d:ない",i);

　　　　((i+1) % 5)? putchar(' ') : putchar('\n');
　　}

　　return 0;
}

int bs(int array[], int size, int mokuteki)
{
　　int ue=size-1, sita=0, naka;

　　while(1){
　　　　naka=(sita+ue)/2;
　　　　if(array[naka] == mokuteki)
　　　　　　return ARU;
　　　　else if(sita > ue) //・・・・・・・★
　　　　　　return NAI;
　　　　else {
　　　　　　if(array[naka] < mokuteki)
　　　　　　　　sita=naka+1;
　　　　　　else
　　　　　　　　ue=naka-1;
　　　　}
　　}
}

========================================================
コピペ用 ↓

========================================================
#include <stdio.h>

enum{ NAI, ARU};
int bs(int array[], int size, int mokuteki);

int main(void)
{
int array[]={1,3,6,13,14,19,19,22,30};
int i,size;
size=sizeof(array) / sizeof(array[0]) ;

for(i=0; i<30; i++){
int ret;
ret=bs(array, size, i);

if(ret == ARU)
printf("%d:ある",i);
else
printf("%d:ない",i);

((i+1) % 5)? putchar(' ') : putchar('\n');
}

return 0;
}

int bs(int array[], int size, int mokuteki)
{
int ue=size-1, sita=0, naka;

while(1){
naka=(sita+ue)/2;
if(array[naka] == mokuteki)
return ARU;
else if(sita > ue) //・・・・・・・★
return NAI;
else {
if(array[naka] < mokuteki)
sita=naka+1;
else
ue=naka-1;
}
}
}