バイナリサーチがうまくいかない

[saiyuki1919]

バイナリサーチをC言語で書こうと思ったのですが、どうしても、うまくいきません。
コンパイラすると、なぜか、一番目の"atto"しか表示してくれません。　keyをかえてもうまくいきません。
環境は、macのxcodeを使って開発しています。

①なぜ、atto のみを算出してしまうのか？
②なぜ、baseにエラーが発生してしまうのか？
この疑問を解いてほしいです。
初心者なので解説よろしくお願いします。

コード:

 char *base[NUM_DATA] = {"atto", "centi", "deca ", "deci ",
    "exa  ", "femto", "giga ", "hecto",
    "kilo ", "mega ", "micro", "milli",
    "nano ", "peta ", "pico ", "tera "
};

int BSearch(char *key,const char base[][NUM_DATA], int bottom, int top)
{
    int middle;
    int temp;
    int i;
    int t;
    if (bottom == top){             /* 探索範囲が０になったら */
        return (-1);     
    
    middle = (top + bottom) / 2;
        t=middle;
        
    temp = strcmp(key, base[middle]);
for(i=0;i<=middle;i++){
    for(t=middle;t<0;t--){
    if (temp == 0){
        return middle;
    
    }else if (temp > 0) {            /* 中央の要素より右を探す */
            if(top == middle + i){
                return(-1);
            }else{
                return(middle+i);
                break;
            }
    }else{
        if(middle-t == 0){
            return(-1);
        }else{
        return(middle-t);
                break;
                                                /* 中央の要素より左を探す */
            //BSearch(key, base, bottom, middle);
        }
    }
    }
}

    }
    return 0;
}

int main(void)
{

    int i;
    int temp;
    char *key="exa";     /* 検索対象の文字列 */
    int top = NUM_DATA - 1;
    int bottom = 0;
    
    printf("キーワード：%s¥n", key);
    printf("検索対象のデータ：%s¥n", key);
    for (i = 0; i < NUM_DATA; i++)
        printf("¥t%s¥n",  base[i]);
    //ここから//
    if ((temp = BSearch(key,base,bottom, top)) != -1){ //<-baseにエラーがでる
        printf("¥n見つかりました: %sは %d 番目の要素です。¥n",base[temp], temp + 1);
    }else{
        printf("¥n見つかりません。¥n");
    }

}

[usao]

line21 > for(t=middle;t<0;t--)
ここが変では？
おそらくこのforの中は一度も走らないような．

＃バイナリサーチって，探索範囲をつぎつぎに半分にしていくんだと思うのですが，
　BSearch()の中って（ざっと眺めただけですが）そういう形になっていないように見えます．

[softya（ソフト屋)]

そもそも、"exa"と"exa "は文字列長が違うので一致することは無いと思います。
あとインデントが狂っているのと、コード全体を公開して頂けないでしょうか？

あとbaseでエラーが出るとのことですが、
const char base[][NUM_DATA]
では型が違います。とりあえず全コードを待ちたいと思います。

[softya（ソフト屋)]

マルチポストのようです。
「大学生なのですがC言語でバイナリサーチを書いたのですがうまくいきません。もしよ... - Yahoo!知恵袋」
http://detail.chiebukuro.yahoo.co.jp/qa ... 1107008571
フォーラムルールなのですが、補足などを使って相互リンクをお願いします。　
※投稿している全掲示板から他に投稿している全掲示板へジャンプできるようにリンクしてもらうことです。つまり、回答者が他の掲示板の回答も確認が出来るようにしてください。

[saiyuki1919]

バイナリサーチをC言語で書こうと思ったのですが、どうしても、うまくいきません。
コンパイラすると、なぜか、一番目の"atto"しか表示してくれません。　keyをかえてもうまくいきません。
環境は、macのxcodeを使って開発しています。

①なぜ、atto のみを算出してしまうのか？
②なぜ、baseにエラーが発生してしまうのか？
この疑問を解いてほしいです。
初心者なので解説よろしくお願いします。

引用します。
http://www1.cts.ne.jp/~clab/hsample/Mem/Mem3.html
このサイトを参考にしました。
私は現在、自動対話プログラムを書こうと思っています。その際に配列から入力した文字を探し、べつの配列からそれに対応する言葉を返すというシステムにしたいのですが、その際にバイナリサーチを利用したいと考えています。
全部のコード乗ると長くなると思うので、これしか載せていません。
いい案があれば聞きたいです。

コード:

 char *base[NUM_DATA] = {"atto", "centi", "deca ", "deci ",
    "exa  ", "femto", "giga ", "hecto",
    "kilo ", "mega ", "micro", "milli",
    "nano ", "peta ", "pico ", "tera "
};

int BSearch(char *key,const char base[][NUM_DATA], int bottom, int top)
{
    int middle;
    int temp;
    int i;
    int t;
    if (bottom == top){             /* 探索範囲が０になったら */
        return (-1);     
    
    middle = (top + bottom) / 2;
        t=middle;
        
    temp = strcmp(key, base[middle]);
for(i=0;i<=middle;i++){
    for(t=middle;t<0;t--){
    if (temp == 0){
        return middle;
    
    }else if (temp > 0) {            /* 中央の要素より右を探す */
            if(top == middle + i){
                return(-1);
            }else{
                return(middle+i);
                break;
            }
    }else{
        if(middle-t == 0){
            return(-1);
        }else{
        return(middle-t);
                break;
                                                /* 中央の要素より左を探す */
            //BSearch(key, base, bottom, middle);
        }
    }
    }
}

    }
    return 0;
}

int main(void)
{

    int i;
    int temp;
    char *key="exa";     /* 検索対象の文字列 */
    int top = NUM_DATA - 1;
    int bottom = 0;
    
    printf("キーワード：%s¥n", key);
    printf("検索対象のデータ：%s¥n", key);
    for (i = 0; i < NUM_DATA; i++)
        printf("¥t%s¥n",  base[i]);
    //ここから//
    if ((temp = BSearch(key,base,bottom, top)) != -1){ //<-baseにエラーがでる
        printf("¥n見つかりました: %sは %d 番目の要素です。¥n",base[temp], temp + 1);
    }else{
        printf("¥n見つかりません。¥n");
    }

}

[saiyuki1919]

はいわかりました。　すみません。

[softya（ソフト屋)]

はいわかりました。　すみません。

謝っていただくよりも早急に実行に写していただければと思います。
それと、全コードが載せられないのであればコンパイルできるようにコンパクトなコードへの加工をお願いします。
これは回答者の役割ではなくsaiyuki1919さんが行うべきことだと私は思います。

[saiyuki1919]

未完成なのですが・・・

コード:

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

#define N 256
#define NUM_DATA 16

char moji[N];
char *base[NUM_DATA] = {"atto", "centi", "deca ", "deci ",
    "exa  ", "femto", "giga ", "hecto",
    "kilo ", "mega ", "micro", "milli",
    "nano ", "peta ", "pico ", "tera "
};



//myf() は、s1で入力した文字列をs2で入力した文字で削除する//
void myf(char *s1, char *s2)
{
    char *p=s1;
    
    p=strstr(p+1,s2);
    if(p!=NULL){
        strcpy(p,p+strlen(s2));
        myf(p+1,s2);
    }
    
}
//入力したも文字を表示し、長さを算出//
int nagasa(char moji[]){
    int i=0;
    while(moji[i] != 0){
        i++;
    }
    printf("かりの長さ%d",i);
    return i;
    
}

//大文字を小文字に変える、アルファベット以外の文字ならスペースに変える//
void mojicheck(char *p) //
{
    while(*p) // '\0'に出会うまで
    {
        if(isalpha(*p)) //アルファベットなら
        {
            if(isupper(*p)) *p=tolower(*p); // 大文字なら小文字に変える
        }
        else // アルファベット以外の文字なら
        {
            *p=' '; // スペースに変える
        }
        p++;
    }
}

//バイナリサーチ//
/////////////////////////////////////////////////////////////////////////////////////////
//配列の中央の要素とキーを比較。                                                            //
//もし等しければ、それが検索対象のデータなので、呼び出し元へ戻る。                                //
//もしキーの方が大きければ、キーは中央の要素より右にあるので、中央の要素＋１から右を探す。            //
//もしキーの方が小さければ、キーは中央の要素より左にあるので、左端の要素から、中央の要素－１までを探す。//
/////////////////////////////////////////////////////////////////////////////////////////

int BSearch(char *key,const char base[][NUM_DATA], int bottom, int top)
{
    int middle;
    int temp;
    int i;
    int t;
    if (bottom == top){             /* 探索範囲が０になったら */
        return (-1);     
    
    middle = (top + bottom) / 2;
        t=middle;
        
    temp = strcmp(key, base[middle]);
for(i=0;i<=middle;i++){
    for(t=middle;t<0;t--){
    if (temp == 0){
        return middle;
    
    }else if (temp > 0) {            /* 中央の要素より右を探す */
            if(top == middle + i){
                return(-1);
            }else{
                return(middle+i);
                break;
            }
    }else{
        if(middle-t == 0){
            return(-1);
        }else{
        return(middle-t);
                break;
                                                /* 中央の要素より左を探す */
            //BSearch(key, base, bottom, middle);
        }
    }
    }
}

    }
    return 0;
}

int main(void)
{

    int i;
    int temp;
    char *key="exa";     /* 検索対象の文字列 */
    int top = NUM_DATA - 1;
    int bottom = 0;
    
    printf("キーワード：%s¥n", key);
    printf("検索対象のデータ：%s¥n", key);
    for (i = 0; i < NUM_DATA; i++)
        printf("¥t%s¥n",  base[i]);
    //ここから//
    if ((temp = BSearch(key,base,bottom, top)) != -1){ //<-エラーがでる
        printf("¥n見つかりました: %sは %d 番目の要素です。¥n",base[temp], temp + 1);
    }else{
        printf("¥n見つかりません。¥n");
    }

}

[softya（ソフト屋)]

消しちゃったんですね。
それはそれであまり良くない行為だとご理解くださいね。

それと私とusaoさんの回答にも書かれたことは理解されていますか？

[saiyuki1919]

まだ、直してないです。
初投稿でわからないことばかりで、すみません。申し訳ないです。

[softya（ソフト屋)]

まだ、直してないです。
初投稿でわからないことばかりで、すみません。申し訳ないです。

直していない事が問題なのではなく、理解されているかって事を気にしています。
１つ１つ、どう理解されているかを書いてもらうのが良いと思います。

[saiyuki1919]

まず、tをデクリメントした理由は、keyの内容をstrcmpで探して、低ければ、左側に移動する。際にmiddleから左によった分を差し引いけば、keyと同じ文字列を探せると思ったからです。
const char base[][NUM_DATA]は、yahoo知恵袋につぶやいた際に最初は、const char base[NUM_DATA]と書いたらエラーが発生してしまいうまくいかなったということをつぶやいたら、このような回答がかえってきたので、これに直したらできたからです。

理解は、しています。

[softya（ソフト屋)]

>そもそも、"exa"と"exa "は文字列長が違うので一致することは無いと思います。
>あとインデントが狂っているのと、コード全体を公開して頂けないでしょうか？

コード全体は対応して頂けましたが、他の2つはスルーされている様です。
こう言う点に気付けないとすると無意識での見逃しが日常茶飯事として行われている事になります。
これが学習する上で結構やっかいです。

>まず、tをデクリメントした理由は、keyの内容をstrcmpで探して、低ければ、左側に移動する。際にmiddleから左によった分を差し引いけば、keyと同じ文字列を探せると思ったからです。

それは既にバイナリーサーチでは無いと思います。
saiyuki1919 さんが理解しているバイナリーサーチを説明してもらってよいでしょうか？

>const char base[][NUM_DATA]は、yahoo知恵袋につぶやいた際に最初は、const char base[NUM_DATA]と書いたらエラーが発生してしまいうまくいかなったということをつぶやいたら、このような回答がかえってきたので、これに直したらできたからです。

大本の参考元のコードは、そうなっていませんよね？
なぜ変えたのでしょうか。

[YuO]

バイナリサーチを初めて書くなら，定義通り再帰で書いた方が書きやすいと思いますよ。
慣れている人であれば，最初から再帰をループに展開して行えますが。

バイナリサーチは，以下の手順になります。

• 先頭インデックスが末尾インデックスより大きければ，みつからなかった
• 探索範囲の中央インデックスを求める
• 探索範囲の中央の配列値と求めたい値を比較する
  • 同じであれば，そのインデックスが求めたい値になる
  • 異なる場合で，探索範囲の先頭インデックスと末尾インデックスが同じであれば，見つからなかった
  • 求めたい値の方が小さければ，先頭インデックスと中央インデックス-1の範囲をバイナリサーチする
  • 求めたい値の方が小さければ，中央インデックス+1と末尾インデックスの範囲をバイナリサーチする

と書いてプレビューしたら追記があったので，それにも反応。

まず、tをデクリメントした理由は、keyの内容をstrcmpで探して、低ければ、左側に移動する。際にmiddleから左によった分を差し引いけば、keyと同じ文字列を探せると思ったからです。

tempの値が一度だけしか設定されていません。
ということは，その一度の比較結果のみで探していることになります。

const char base[][NUM_DATA]は、yahoo知恵袋につぶやいた際に最初は、const char base[NUM_DATA]と書いたらエラーが発生してしまいうまくいかなったということをつぶやいたら、このような回答がかえってきたので、これに直したらできたからです。

難しいことは考えず，仮引数の型と実引数の型は同じにするか，constをつけるのみにしてください。
今回は，

コード:

char *base[NUM_DATA]

に対応するのだから，

コード:

int BSearch(char *key,char *base[NUM_DATA], int bottom, int top)

のように書けばよいです。

理解は、しています。

バイナリサーチは探索範囲をどんどん半分にしていくことによって，O(log n)の計算量で検索を行うアルゴリズムです。
その，「半分にしていく」というキモの部分を理解していますか。
コードからは，理解していることが確認できませんでした。

と書いてプレビューしたらさらに追記があったけれども，saiyuki1919さんのものではないのでそのまま投稿します。
# 私の書いた内容がsoftya（ソフト屋)さんの配慮を無にしている気がしなくもないですが……。

---- 編集 ----
@2013-05-10T18:28+09:00ころ
旧) と書いてプレビューしたらさらに追記があったけれども，saiyuki1919さくさんのものではないのでそのまま投稿します。
新) と書いてプレビューしたらさらに追記があったけれども，saiyuki1919さんのものではないのでそのまま投稿します。

[saiyuki1919]

>そもそも、"exa"と"exa "は文字列長が違うので一致することは無いと思います。
完全に凡ミスでした。かえてみたのですが、駄目でした。

>あとインデントが狂っているのと、コード全体を公開して頂けないでしょうか？
インデント狂っていてすみません。xcodeで書いていたので・・
コードは、途中までしか書いてないので、これで全部です。
ともかく、バイナリサーチで文字列を検索して、存在するのか存在しないのか、配列のどこにあるのかを調べられれば十分です。

>大本の参考元のコードは、そうなっていませんよね？なぜ変えたのでしょうか。
コードがわかりずらいなって思ったのと、自分の力で書きたかっただけです。

[saiyuki1919]

たった今理解しました。YuOありがとうございます。
バイナリサーチを勘違いしてました。
ちょっと書き直してみます。

[softya（ソフト屋)]

>そもそも、"exa"と"exa "は文字列長が違うので一致することは無いと思います。
完全に凡ミスでした。かえてみたのですが、駄目でした。

どうダメなのでしょうか？　そして、かえてみたの事がなぜダメだったかどうやって検証されましたか？

>あとインデントが狂っているのと、コード全体を公開して頂けないでしょうか？
インデント狂っていてすみません。xcodeで書いていたので・・
コードは、途中までしか書いてないので、これで全部です。
ともかく、バイナリサーチで文字列を検索して、存在するのか存在しないのか、配列のどこにあるのかを調べられれば十分です。

xcodeってインデント不要なんでしょうか？
始めて伺いましたが設定ミスって事はありませんか？

>大本の参考元のコードは、そうなっていませんよね？なぜ変えたのでしょうか。
コードがわかりずらいなって思ったのと、自分の力で書きたかっただけです。

そうですね。引数がちゃんと受け渡されているかデバッガの利用とprintfデバッグ法を勉強されたほうが良いと思います。
引数の受け渡しを確認されていませんよね？
デバッガはxcodeなのでよく存じませんが、gdbが使えるんじゃないかと。

「もう一度基礎からC言語 第13回 エラーメッセージと対処方法(３)～開発手順の効率化 printfデバッグを試す」
http://www.grapecity.com/tools/support/ ... page04.htm

私の書いたものですが、Windows特有の部分は無視してください。
「簡単RPG講座　番外編。　デバッグ入門 • C言語交流フォーラム　～ mixC++ ～」
http://dixq.net/forum/blog.php?u=114&b=982&c=2

[１９１９]

今更ですか、バイナリサーチうまくいきました。ありがとうございます。

[softya（ソフト屋)]

解決して何よりです。
ただ、この掲示板の義務事項として最終的なコードの投稿をお願い出来ますでしょうか。
あと名前を変えるのもルール違反となっております。