二分探索について質問です。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 二分探索について質問です。

Re: 二分探索について質問です。

#7

by 初心マン » 8年前

かずま様
既存のソースコードに手を加えていただいたおかげでとても分かりやすかったです！
ありがとうございました！

Re: 二分探索について質問です。

#6

by 初心マン » 8年前

math様
ソースコード拝見いたしました。
参考にさせていただきます！
ありがとうございました！

Re: 二分探索について質問です。

#5

by 初心マン » 8年前

みけCAT様
minとmaxを初期化したら動くようになりました。
ありがとうございました！

Re: 二分探索について質問です。

#4

by かずま » 8年前

初心マン さんが書きました:これはなぜ起こるのでしょうか。解決策を教えてください。
★の部分が抜けているからでしょう。

コード: 

#include <stdio.h>

#define MAXDATA 10000

int main(void)
{
    int x, a[MAXDATA];
    int n;
    char filename[200];
    FILE *fin;
    int i, j, k, tmp;
    int min, max, mid;

    printf("file name = ");
    scanf("%s", filename);
    if ((fin = fopen(filename, "r")) == NULL) {
        printf("ファイルをオープンできません\n");
        return 1;
    }
    n = 0;
    while (fscanf(fin, "%d", &a[n]) == 1) n++;
    fclose(fin);

    for (i = 0; i < n-1; i++) {
        j = i;
        for (k = i+1; k < n; k++) {
            if (a[j] > a[k]) j = k;
        }
        tmp = a[i], a[i] = a[j], a[j] = tmp;  // ★
    }                                         // ★

    while (scanf("%d", &x) == 1) {
        min = 0;                              // ★
        max = n - 1;                          // ★
        while (min <= max) {
            mid = (min + max) / 2;
            if (a[mid] == x) {
                break;
            } else if (a[mid] < x) {
                min = mid + 1;
            } else if (a[mid] > x) {
                max = mid - 1;
            }
        }
        if (a[mid] == x) {
            printf(" x=%d ---> %d\n", x, mid);
        } else {
            printf("見つかりませんでした。\n");
        }
    }
    printf("またお会いしましょう\n");
    return 0;
}
インデントに注意してください。

Re: 二分探索について質問です。

#3

by Math » 8年前

関数があったので　(Windows10,VS2017Community,開発者用コマンドプロント,TeraPadを使用）
それを使えばわかりやすいかな。
［c1.c］

コード: 

#include <stdio.h>
#include <stdlib.h>
#define KEY_NOT_FOUND 9999

int binary_search(int ary[], int key, int imin, int imax) {
    if (imax < imin) {
        return KEY_NOT_FOUND;
    } else {
        int imid = imin + (imax - imin) / 2;
        if (ary[imid] > key) {
            return binary_search(ary, key, imin, imid - 1);
        } else if (ary[imid] < key) {
            return binary_search(ary, key, imid + 1, imax);
        } else {
            return imid;
        }
    }
}

int main(void){
    int ans;
    int ary[]={ 1,2,6,43,123, };
    int key;
    while(1){
        scanf("%d", &key);
        ans=binary_search(ary, key, 0, 5-1);
        if(ans==9999){printf("KEY_NOT_FOUND\n");}
        else{printf("result : ary[%d]=%d\n",ans,ary[ans]);}
    }

    return 0;
}
[c.bat]

コード: 

rem コンパイル後リンク
cl /TC c1.c
rem 実行結果
c1.exe
実行結果

コード: 

D:\z17c\c\0718>c

D:\z17c\c\0718>rem コンパイル後リンク

D:\z17c\c\0718>cl /TC c1.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.10.25019 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

c1.c
Microsoft (R) Incremental Linker Version 14.10.25019.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:c1.exe
c1.obj

D:\z17c\c\0718>rem 実行結果

D:\z17c\c\0718>c1.exe
1
result : ary[0]=1
2
result : ary[1]=2
6
result : ary[2]=6
43
result : ary[3]=43
123
result : ary[4]=123
125
KEY_NOT_FOUND
2
result : ary[1]=2
43
result : ary[3]=43
^Cバッチ ジョブを終了しますか (Y/N)?

Re: 二分探索について質問です。

#2

by みけCAT » 8年前

ソースコードを提示する際は、BBCodeが有効な(無効にしない)状態で、
BBCodeのcodeタグの開始タグと終了タグの組(開始タグが先)で囲んでいただけると、
見やすくてありがたいです。
また、インデントもきちんと整えるといいでしょう。

さらに、提示されているコードはコンパイルが通らなかったので、最後に}を追加したコードでテストしました。
初心マン さんが書きました:二回目まではしっかりとループして指定した数値がどこに配置しているのか教えてくれますが、三回目以降は「見つかりませんでした」の表示しかされません。
再現できませんでした。1を入力し続けると、何回目でもきちんと見つかるようでした。
ただし、1を何回か入力 → 2を何回か入力 → 6を入力 とすると、「見つかりませんでした」が出ました。
初心マン さんが書きました:これはなぜ起こるのでしょうか。
minおよびmaxをきちんと初期化せずに探索を繰り返しているからだと思います。
初心マン さんが書きました:解決策を教えてください。
scanfで探索する値を読み込んだ後、whileループで探索を開始する前に、minを0、maxをn-1で初期化するといいと思います。

二分探索について質問です。

#1

by 初心マン » 8年前

c言語初心者です。二分探索法のソースコードを書いてみたのですがwhile以下でのループに異状があります。二回目まではしっかりとループして指定した数値がどこに配置しているのか教えてくれますが、三回目以降は「見つかりませんでした」の表示しかされません。これはなぜ起こるのでしょうか。解決策を教えてください。ファイルの中身は「１　２　６　４３　１２３」の五つです。
#include <stdio.h>
#include <stdlib.h>
#define MAXDATA 10000

int main(void)
{
int x, a[MAXDATA];
int n, i;
char filename[20];
FILE *fin;
int j, k;
int tmp;
int number=sizeof(filename)/sizeof(int);
int min = 0;
int max = number-1;
int mid;

printf("file name = ");
scanf("%s", filename);
if ((fin=fopen(filename, "r"))==NULL) {
printf("ファイルをオープンできません\n");
return (1);
}
n=0;
while (fscanf(fin, "%d", &a[n])==1) n++;
fclose(fin);

for(i=0; i < n-1; i++){
j=i;
for(k=i+1; k < n; k++){
if (a[j] > a[k]){j=k; }
}
while (scanf("%d", &x)==1) {

while(min <= max ) {
mid = (min + max) / 2;
if (a[mid]==x) {
break;
} else if (a[mid] < x) {
min = mid + 1;
} else if (a[mid] > x){
max = mid - 1;
}
}
if(a[mid]==x){
printf(" x=%d ---> %d\n",x ,mid );

}
else {
printf("見つかりませんでした。\n",x);

}

}
printf("またお会いしましょう\n");
return (0);
}

ページトップ