いつもお世話になっています。
現在他人のプログラムを読解する力をつけようと
訓練しています。
以下の文はとあるアルゴリズム本の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で学ぶアルゴリズムとデータ構造」
という本です。だいたい一通り読みましたが読んでて
楽しいしわかりやすいし良書だと思います。高価ですが・・・。
No.5ベストアンサー
- 回答日時:
再度ループさせる必要な無いしょう。
size が 0 であるリストを探索することもありますから、どちらにしても、先にarray[naka]を判定をするのは良くないです。
少し飛躍しますが、見つからなかった時にリストに追加しなければならない場合がありますよね?
soakunさんの例だと、ループを抜けた後に、l がそのまま挿入インデックスになるので都合がいいです。
個人的な趣味だと、break しているところは、return が好きなんですけど。
待ちに待った「自身あり」の肯定意見をありがとうございます。
さらにアルゴリズムの間違いまで指摘してくれてとても助かりました。
>size が 0 であるリストを探索することもありますから、
ごもっともです。もしそんなことしてたら
割り当てられてない記憶領域へアクセスさせて
クラッシュしてしまう所でした。
すばらしすぎます。どうやったらそこまで
見抜く力が付くのでしょうか?
No.3
- 回答日時:
>ところでsoakunさんのプログラムに誤りらしきものが・・(^^;
あぅ、どこが間違いなのでしょう?(^^;
# もしかしたらここを見る人のためにも修正したいので補足よろしゅー
この回答への補足
はい。入力ミスっぽいのとうっかりミスっぽいのがありました。
(1)while(l > h)
これの符号は逆ですよね。
(2)while(・・){
if(array[t] == mokuteki)
break;
}
return (l > h) ? t : (-1);
目的値が見つかっても負を返しちゃいますよね。
間違ってたらごめんなさいです。(~~)/~
No.2
- 回答日時:
二分木探索について手元にあるアルゴリズム書から
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
- 回答日時:
sitaとueが同じ値になり、目的値が見つからなかったのに再度ループする必要はないと思いますが、
以前に、同じようなプログラムを書いたとき、sita >= ue では正しく動かなかったような記憶があります。
この回答への補足
ご意見たいへんありがとうございます。
動作を確認できそうなプログラムを作成してみました。
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;
}
}
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
カードシャッフルのブログラム...
-
intとlongは同じ?
-
OpenCVによる4値化について
-
組織的ディザ法のプログラムが...
-
コマンドプロンプトのウィンド...
-
2の補数を計算するプログラム
-
C言語で%を使わない余りの出し方
-
C#メール受信から件名、本文を...
-
プログラミングに関して
-
C++ Debug Errorについて教えて
-
3のつく数と3の倍数を表示 C言語
-
再起呼び出しの回数をカウント...
-
画像の拡大・縮小
-
DXライブラリによるパズルゲー...
-
【C#】SQL文の中に変数を埋め込...
-
二分探索アルゴリズムの終了条...
-
異なるn個の整数からr個の整数...
-
再帰処理をループ処理に変換
-
C++で表を作成したいのです ...
-
分数の足し算をさせるプログラ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
intとlongは同じ?
-
2の補数を計算するプログラム
-
再起呼び出しの回数をカウント...
-
C++ bmp 透過処理
-
OpenCVによる4値化について
-
カードシャッフルのブログラム...
-
C言語で%を使わない余りの出し方
-
argvのNULLチェック
-
コマンドプロンプトのウィンド...
-
分数の足し算をさせるプログラ...
-
関数とビット列
-
ヌメロンのプログラム
-
whileとifを使い偶数を出すには
-
迷路を脱出する経路探索プログ...
-
プログラミングに関して
-
C++で表を作成したいのです ...
-
C言語で簡単なパックマンゲーム...
-
| (or) を使った関数の引数の作...
-
条件が多い場合
-
複数の共有メモリの作成
おすすめ情報