二分探索がうまくいきません

前提・実現したいこと

C言語で二分探索を実装したいです。
配列の中に探索している値があれば、配列の○番目で発見したと画面に表示したいです。

発生している問題・エラーメッセージ

配列の中に探索している値があるにもかかわらず、発見したと表示されません。

該当のソースコード

C
1#include <stdio.h>
2int main(void){//二分探索法
3
4    int array[7]={1,3,5,7,9,11,13};
5    int lo=0, mid, hi=6;
6    int val=11;//探索したい値
7
8    while(lo > hi){
9        mid = (lo + hi) / 2;
10        if(array[mid] < val){
11            lo = mid + 1;
12        }else if(array[mid] > val){
13            hi = mid - 1;
14        }else{
15            printf("値「%d」は配列の[%d]番目で発見しました",val,mid);
16        }
17    }
18}

試したこと

おそらくwhile文内のif分岐が正しくないと推測し、修正していますがうまくいきません。

C
1if(array[mid] < val){
2            lo = mid + 1;
3        }if(array[mid] > val){
4            hi = mid - 1;
5        }if(array[mid] == val){
6            printf("値「%d」は配列の[%d]番目で発見しました",val,mid);
7        }

↑これもうまくいかなかった例です。

補足情報（FW/ツールのバージョンなど）

実行環境はpaiza.ioです。

###修正中のコード
頂いた回答をもとに修正しました。探索したい値(val)が3,7,11なら正常に探索結果が表示され、
1,5,9,13なら、何も表示されない状況です。まだうまく動作しません。以下修正中のコードです。

C
1#include <stdio.h>
2
3int main(void){//二分探索法
4
5    int array[7]={1,3,5,7,9,11,13};
6    int lo=0, mid, hi=6;
7    int val=11;//探索したい値
8
9    while(lo < hi){//継続条件修正済み
10        mid = (lo + hi) / 2;
11        if(array[mid] < val){
12            lo = mid + 1;
13        }else if(array[mid] > val){
14            hi = mid - 1;
15        }else{
16            printf("値「%d」は配列の[%d]番目で発見しました",val,mid);
17            break;//追記
18        }
19    }
20}

行動規範の内容に同意します

回答5件

while (lo <= hi) にしないと、要素数が 1 になったとき、その値を見ることができません。

追記

C
1#include <stdio.h>
2
3void search(int val)
4{
5    int array[7] = { 1, 3, 5, 7, 9, 11, 13 };
6    int lo = 0, mid, hi = 6;
7
8    while (lo <= hi) {  // (lo < hi) だと結果が不正
9        mid = (lo + hi) / 2;
10        if (array[mid] < val)
11            lo = mid + 1;
12        else if(array[mid] > val)
13            hi = mid - 1;
14        else {
15            printf("値「%d」は配列の[%d]番目で発見しました。\n", val, mid);
16            break;
17        }
18    }
19	if (lo > hi) 
20        printf("  値「%d」は発見できませんました。\n", val);
21}
22
23int main(void)
24{
25	for (int val = 0; val < 15; val++)
26		search(val);
27}

あなたの修正したコードとどこが違っていますか？

投稿2020/07/25 05:59

編集2020/07/26 03:01

kazuma-s

総合スコア8224

hana_yama_san

2020/07/25 06:59 編集

仰るとおりですが、質問者の修正済コードの場合、最初のループでmidが3になり次のループで5になるため、array[5] == 11で終了するはずです。私の環境ではうまく動きました。 [user@host]c-work/work> ./BinSearch 値「11」は配列の[5]番目で発見しました[user@host]c-work/work> なぜうまく動かないのでしょうね。＞＞質問者さんへ、printfの出力末尾は改行を入れましょう。

ceg34ry

2020/07/26 02:45

質問者です、お世話になります。 kazuma-s様へわかりました継続条件を、そのようにします。 hana_yama_san様へ＞私の環境ではうまく動きました。＞値「11」は配列の[5]番目で発見しました[user@host]c-work/work> 上記のとおり試してくださったとの事ですが、探索したい値を1,5,9,13のどれかに指定して動きましたでしょうか。私はpaizaとcode chefの二つの環境で試しましたが動きません。 [実行環境] https://paiza.io/ja/projects/new https://www.codechef.com/ide

hana_yama_san

2020/07/26 08:56

私はFreeBSD12.1のclangを使用しました。 [user@host]c-work/work> cat binsearch.c #include <stdio.h> int main(void){//二分探索法 int array[7]={1,3,5,7,9,11,13}; int lo=0, mid, hi=6; int val=13;//探索したい値 while(lo <= hi){//継続条件修正済み mid = (lo + hi) / 2; if(array[mid] < val){ lo = mid + 1; }else if(array[mid] > val){ hi = mid - 1; }else{ printf("値「%d」は配列の[%d]番目で発見しました\n",val,mid); break;//追記 } } } [user@host]c-work/work> [user@host]c-work/work> [user@host]c-work/work> clang binsearch.c -o BinSearch [user@host]c-work/work> [user@host]c-work/work> [user@host]c-work/work> ./BinSearch 値「13」は配列の[6]番目で発見しました [user@host]c-work/work> [user@host]c-work/work> [user@host]c-work/work> [user@host]c-work/work> cat binsearch.c #include <stdio.h> int main(void){//二分探索法 int array[7]={1,3,5,7,9,11,13}; int lo=0, mid, hi=6; int val=3;//探索したい値 while(lo <= hi){//継続条件修正済み mid = (lo + hi) / 2; if(array[mid] < val){ lo = mid + 1; }else if(array[mid] > val){ hi = mid - 1; }else{ printf("値「%d」は配列の[%d]番目で発見しました\n",val,mid); break;//追記 } } } [user@host]c-work/work> [user@host]c-work/work> [user@host]c-work/work> clang binsearch.c -o BinSearch [user@host]c-work/work> [user@host]c-work/work> [user@host]c-work/work> ./BinSearch 値「3」は配列の[1]番目で発見しました [user@host]c-work/work>

kazuma-s

2020/07/26 09:10

FreeBSD12.1のclang では動いて、paizaとcode chefの二つの環境では動かないということですか？

hana_yama_san

2020/07/26 09:54

paiza 初めて知りましたが、試したところうまく動きましたよ。スクリーンショットをとったのですが、コメントでは添付出来ないので、回答欄を使用しますね。

行動規範の内容に同意します

c
1    while(lo > hi){

これ
int lo=0, mid, hi=6;
なんだから即falseになって抜けますよね。

※これ直しても永久ループするだろうけど理由としてはlo hiの値が変わらないから…とだけ

投稿2020/06/14 08:02

rururu3

総合スコア5545

ベストアンサー

paizaのスクリーンショットを添付しますね。

投稿2020/07/26 09:56

hana_yama_san

総合スコア923

C
1#include <stdio.h>
2int main(void){//二分探索法
3
4    int array[7]={1,3,5,7,9,11,13};
5    int lo=0, mid, hi=6;
6    int val=10;//探索したい値
7
8    while(lo < hi){ // [修正]
9        mid = (lo + hi) / 2;
10        if(array[mid] < val){
11            lo = mid + 1;
12        }else if(array[mid] > val){
13            hi = mid - 1;
14        }else{
15            printf("値「%d」は配列の[%d]番目で発見しました",val,mid);
16            break; // [追加]
17        }
18    }
19}