c言語 for の無限ループ回避の理由

Question

コード同士のどの部分が影響を及ぼすのか理解できず困っています。
こちらの（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp）を問題に対して以下のように解答しました。
コードとしては一方の配列に含まれる値をもう一つの配列から二分探索を行うものなのですが、途中でforの無限ループが発生してしまいます。
以下コードになります。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int binary(int a[],int left,int right,int x){
    int middle=(left+right)/2;
    if(x==a[middle]) return 1;

    while(left != right) {
        if(x<a[middle])binary(a, left, middle,x);

        if(x>a[middle])binary(a, middle+1,right,x);
    }
    return -1;
}

int main(){
int i, j,n,m;

scanf("%d",&n);
printf("%d",n);
int s[n];
for(i=0;i<n;i++){
    scanf("%d",&s[i]);
    printf("Ok");
}

scanf("%d",&m);
printf("%d",m);
int t[m];
for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}
printf("読み込み終わり");
int x,ans,count;
count=0;
for (i = 0; i < m;i++) {
    x=t[i];
    ans=binary(s,0,n,x);
    if(ans==1)count++;
    }
printf("%d",count);
    return 1;
}

具体的にはコンパイル時に２つ目のfor scanf

for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}

で無限ループをしました。
そこでコードを触ってみたところ、
「printf("読み込み終わり");」を以下を消した場合だと何故か

for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}

の先程のループがとまり、「printf("読み込み終わり");」に到達したあとプログラムが終了します。
この理由がわかりません。

削除後のコードは以下になります。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int binary(int a[],int left,int right,int x){
    int middle=(left+right)/2;
    if(x==a[middle]) return 1;

    while(left != right) {
        if(x<a[middle])binary(a, left, middle,x);

        if(x>a[middle])binary(a, middle+1,right,x);
    }
    return -1;
}

int main(){
int i, j,n,m;

scanf("%d",&n);
printf("%d",n);
int s[n];
for(i=0;i<n;i++){
    scanf("%d",&s[i]);
    printf("Ok");
}

scanf("%d",&m);
printf("%d",m);
int t[m];
for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}
printf("読み込み終わり");
    return 1;
}

その後デバッグツールを使い、変数の確認等を行いましたが、
x>hit を満たしているのにもかかわらず再帰せずreturn -1に到達してしまいます。
x=4,hit=3である以上
if(x > hit){binary(a, middle+1,right,x);}
で再帰すると思うのですがなぜか再帰しません。（
画像のように１３行目で再帰せずに１４行目に抜けてしまいます。
これはなぜなのでしょうか？

今現在のコードは以下のようになります。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 二分探索　ｘは探したい値 */
int binary(int a[],int left,int right,int x){
    int middle=(left+right)/2;
    if(x==a[middle]) return 1;

    if(left<right){
        int hit=a[middle];
        if(hit > x){binary(a, left, middle, x);}

        if(x >  hit){binary(a, middle+1,right,x);}
      }
    return -1;
}

int main(){
int i,n,m;

scanf("%d",&n);
int s[n];
for(i=0;i<n;i++){
    scanf("%d",&s[i]);

    /* 配列ｓの作成 */

}

scanf("%d",&m);
int t[m];
for(i=0;i<m;i++){
    scanf("%d",&t[i]);

/* 配列tの作成 */
}

int x,ans,count;
count=0;/* 見つかった回数カウント */
for (i = 0; i < m;i++) {
    x=t[i];
    ans=binary(s,0,n-1,x);
    if(ans==1)count++;
    }
    printf("%d",count);
    return 1;
}

Comments

[pepperleaf]

初回、binary()に入ったところから、ステップ実行した結果でしょうか?
(1/8 のコードで、、、)
続いて、ステップ実行続けても同様でしょうか?
時折、デバッガはウソつくことがあるので注意が必要。(最適化等の問題)

[退会済みユーザー]

正確に説明するとi=0のときは
if(left<right)に到達せずにそのままreturnとなります
i=1のときにそのような現状が起きます

実行は最初から実行し、ブレークポイントを置いた形です

[pepperleaf]

このデバッガ使った事が無いので、見方が分かりませんが、赤●がブレークポイント? で、再帰の判定はどうしてるのでしょうか?
データが不明なので、正確には分かりませんが、再帰はしていて、
> if(x==a[middle]) return 1;
ここで戻ってるって事はありませんか?　上記、書き忘れましたが、ステップ実行の場合、関数内の処理では、ブレークポイントが無いと止まりません。 確認するならば、関数の先頭にブレークポイントが必要です。 (または、ステップインの設定)

[pepperleaf]

あ、書き忘れましたが、 binary()関数、main()から、呼ばれ、最初に
> if(x==a[middle])
が成立すれば、1 を返しますが、それ以外は全て、-1 となります。なぜなら、binary()を再帰で呼んでいますが、その戻り値は常に無視され、最後の
> return -1;
となります。 この辺の理解は間違い無いでしょうか?

Answer 1

こんにちは。

具体的にはコンパイル時に２つ目のfor scanf（中略）で無限ループをしました。

この判断ミスだろうと思います。
printf()の出力はキャッシュされますので、キャッシュをフラッシュする、ある程度出力が貯まる、プログラムが正常終了する等の事象が発生するまで出力されません。なので、無限ループや落ちた時に単純なprintfですとその場所を見誤ることが多いです。
各printfの後ろにfflush(stdout);をおいてみて下さい。printfの後キャッシュを直ぐにフラッシュするので直ぐに出力されるようになります。

ざっと見る限り無限ループを回っているのは binary関数の可能性が高そうです。

Comments

[退会済みユーザー]

皆様の意見にbinary の方にループがあるのと、printfは到達時にすぐ出力されてることを知っておらず、binaryの部分で修正を試みることに致しました。

[pepperleaf]

あ、気が付かなかったですが、printf()の出力に "\n" が無い。
ほぼ、確実にキャッシュされますね。(仕様かどうかは知りませんが、、、)
printf("%d\n", n) とかするだけで、出力されると思います。

Answer 2

EclipseやVisualStudioを入れると、Cのコードで任意の場所で止めて、変数の内容を確認したり、ワンステップづつ実行させてどういう動作をするか確認できるようになります。
こういうので自分のコードの動作を確認なされてはどうでしょう
あてずっぽでコードを書かなくて済むようになります

Comments

[退会済みユーザー]

macの都合上、visual studioが使えずCLionというIDEを使っていたのですがEclipse検討してみます（ワンステップずつ実行できる機能の存在を存じておりませんでした。）

[y_waiwai]

Cでコードを組む場合、そういうデバッガ無しでコードを組むのは無謀と言っていいと思います
C言語というのは、コードにエラーがあっても、止まらない、おかしな動作をする、場合によっては正常に動いているような動作をする、というモノなので、推測や当てずっぽでは、初心者が正しいコードを組むのは至難の業となります

＃Pythonなどでは、おかしなコードでは確実に止まってくれます

[alphya]

（CLionはとてもいいIDEですよ！！ステップ実行もできるはずです！！
参考→https://pleiades.io/help/clion/debugging-code.html ）

[退会済みユーザー]

alphyaさん

Clionのデバッグツールを導入し、使わせて頂いています！
ありがとうございます

Answer 3

    while(left != right) {
        if(x<a[middle])binary(a, left, middle,x);

        if(x>a[middle])binary(a, middle+1,right,x);
    }

この部分で無限ループ発生しませんか?
while ループ内で、left, right が更新されていません。
もしかしたら、

if () return binary();

の間違い?

無限ループ箇所の確認はどのように行ったのでしょう。

Comments

[退会済みユーザー]

Chironianさんのコメントにもつながるのですが、printfの出力タイミンでループの確認を行っていました（今回だとokや読み込み終わりの出力）
whileループは他の方のコメントにもありますように今修正を試みています。

Answer 4

詳しく見ておりませんが、現象からして未定義状態になっている可能性があります。これは、C言語の仕様外の状態のことであり、再現性のないバグとして表面化するパターンが多いです。

ループの中でn,m,i,s[i],t[i]の値の経過を見てみるといいと思いますよ。

Comments

[HogeAnimalLover]

とりあえず、バイナリサーチ関数の再帰呼び出しの部分はおかしいですね。whileループと再帰を併用している上に、戻り値伝搬がないです。