OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

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

  • 困ってます
  • 質問No.156934
  • 閲覧数468
  • ありがとう数4
  • 気になる数0
  • 回答数5
  • コメント数0

お礼率 87% (76/87)

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

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

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

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の状態ならば、幅1の範囲がありますから
 ループをもう一回実行する必要があります。」
と書いています。私には理解できません。


ちなみにこの本は「Javaで学ぶアルゴリズムとデータ構造」
という本です。だいたい一通り読みましたが読んでて
楽しいしわかりやすいし良書だと思います。高価ですが・・・。
通報する
  • 回答数5
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.5

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

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

個人的な趣味だと、break しているところは、return が好きなんですけど。
お礼コメント
aaaaa

お礼率 87% (76/87)

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

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

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

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

すばらしすぎます。どうやったらそこまで
見抜く力が付くのでしょうか?
投稿日時 - 2001-10-28 07:35:38
-PR-
-PR-

その他の回答 (全4件)

  • 回答No.1
レベル8

ベストアンサー率 16% (9/55)

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

お礼率 87% (76/87)

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

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

★の部分を
  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;
}
}
}
投稿日時 - 2001-10-25 01:58:44
  • 回答No.2
レベル6

ベストアンサー率 66% (6/9)

二分木探索について手元にあるアルゴリズム書から Cに書きおこしたものを書いてみます。 # この段階で上のプログラムと若干異なっているのですが(^^; int bs(array, size, mokuteki) int *array; int size; int mokuteki; { int l = 0; int h = size - 1; int t; ...続きを読む
二分木探索について手元にあるアルゴリズム書から
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");
}
}
お礼コメント
aaaaa

お礼率 87% (76/87)

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

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

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

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

「うん、そうだね。」とうなずいていただけると嬉しいのですが・・・
投稿日時 - 2001-10-27 07:48:52
  • 回答No.3
レベル6

ベストアンサー率 66% (6/9)

>ところでsoakunさんのプログラムに誤りらしきものが・・(^^; あぅ、どこが間違いなのでしょう?(^^; # もしかしたらここを見る人のためにも修正したいので補足よろしゅー ...続きを読む
>ところでsoakunさんのプログラムに誤りらしきものが・・(^^;

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

お礼率 87% (76/87)

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

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

(2)while(・・){
    if(array[t] == mokuteki)
      break;
   }
   return (l > h) ? t : (-1);

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

間違ってたらごめんなさいです。(~~)/~
投稿日時 - 2001-10-27 19:49:15
  • 回答No.4
レベル6

ベストアンサー率 66% (6/9)

あう、そのとおりです(たはは~(汗 ご指摘どおり、不等号が逆転してますです; ...続きを読む
あう、そのとおりです(たはは~(汗
ご指摘どおり、不等号が逆転してますです;
お礼コメント
aaaaa

お礼率 87% (76/87)

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

私のこんなひねくれた質問を読んで考えてくださった
方々全員に感謝いたします。
投稿日時 - 2001-10-28 07:34:37
このQ&Aのテーマ
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ