ページ 1 ／ 1
C言語 バイナリサーチについて
Posted: 2015年10月18日(日) 00:55
by kaovines
こんばんは。
設定した配列に対して（要素は知らないものとする）探したい値が配列内にあればその添字を、なければ-1を返したいです。
現状はgccでコンパイルすると32:2: error: initializer element is not constant static int right = n - 1;とエラーが表示されます。
これは変数の値を代入することで初期化はできないということは理解しているつもりなのですが手詰まりでどうしようもない状態です。
引数int b_search(int x, int v[], int n)はこの表現のもとでどのようにしたらよいのかご教授お願いします。
コード:
#include<stdio.h>
int b_search(int x, int v[], int n);
int main(void)
{
int v[] = {1, 3, 5, 8, 12, 16, 19, 24, 26, 31, 35, 38, 40, 46, 47, 51, 63}; /* 配列を設定 */
int number = sizeof(v)/sizeof(int); /*配列の要素数を計算*/
int x, z;
printf("探したい値を入力してください:");
scanf("%d", &x);
z = b_search(x, v, number);
if(z == -1)
{
printf("存在しないので-1が返された\n");
}
else
{
printf("%dの場所は%d番目である\n", x, z);
}
return 0;
}
int b_search(int x, int v[], int n)
{
static int left = 0;
static int right = n - 1;
int m;
if(left > right)
{
return -1;
}
m = (left + right)/2;
if(left == right)
{
return -1;
}
if(x == v[m])
{
return m;
}
else if(x < v[m])
{
right = m - 1;
return b_search(x, v, right);
}
else
{
left = m + 1;
return b_search(x, v, left);
}
return 0;
}
Re: C言語 バイナリサーチについて
Posted: 2015年10月18日(日) 02:36
by hide
では、理解したとおりに定数で初期化すればいいのでは？
コード:
static int right = - 1;
right += n;
仕様見たわけでは無いですが、
関数内に定義していてもstaticな変数は関数の実行時ではなくプログラムの実行時あたりに初期化が走るとことになっていると思います。
故に、プログラムの実行時には n が見えていないのでダメなのでしょう。
Re: C言語 バイナリサーチについて
Posted: 2015年10月18日(日) 03:04
by YuO
kaovines さんが書きました:現状はgccでコンパイルすると32:2: error: initializer element is not constant static int right = n - 1;とエラーが表示されます。
これは変数の値を代入することで初期化はできないということは理解しているつもりなのですが手詰まりでどうしようもない状態です。
ではなくて，staticな変数は定数式か文字列リテラルでしか初期化できない，というものです。
ISO/IEC 9899:2011 / 6.7.9 Initializer / ¶4
All the expressions in an initializer for an object that has static or thread storage duration shall be constant expressions or string literals.
上記にあるように，staticや_Thread_localが特殊なのであって，そうでなければ，変数を使って初期化することも可能です。
そもそも，変数leftとrightをstaticにしているのはなぜでしょうか。
kaovines さんが書きました:引数int b_search(int x, int v[], int n)はこの表現のもとでどのようにしたらよいのかご教授お願いします。
- 再帰で実装したいのであれば，leftとrightを引数にとる下請け関数を用意し，その関数が再帰するように実装する
- そもそも二分探索はループで実装できるのだから，ループで実装する
あたりが解決策かと。
leftとrightはb_searchの引数(x, v, n)の組に対しての処理中の状態なのですから，staticに持つのは普通の実装ではないと思います。
Re: C言語 バイナリサーチについて
Posted: 2015年10月18日(日) 14:21
by kaovines
YuO さんが書きました:
kaovines さんが書きました:引数int b_search(int x, int v[], int n)はこの表現のもとでどのようにしたらよいのかご教授お願いします。
- 再帰で実装したいのであれば，leftとrightを引数にとる下請け関数を用意し，その関数が再帰するように実装する
- そもそも二分探索はループで実装できるのだから，ループで実装する
あたりが解決策かと。
leftとrightはb_searchの引数(x, v, n)の組に対しての処理中の状態なのですから，staticに持つのは普通の実装ではないと思います。
下請け関数を用意し、その関数が再帰するように実装するとうまくいきました。
staticに関してはまだまだ仕様がわかっていませんが、今回使うことは不自然なことは理解したと思います。
わかりやすい回答有り難うございました。
Re: C言語 バイナリサーチについて
Posted: 2015年10月18日(日) 15:02
by かずま
YuO さんが書きました:
ISO/IEC 9899:2011 / 6.7.9 Initializer / ¶4
All the expressions in an initializer for an object that has static or thread storage duration shall be constant expressions or string literals.
上記にあるように，staticや_Thread_localが特殊なのであって，そうでなければ，変数を使って初期化することも可能です。
その通りですが、念のため補足説明をしておきます。
"an object that has static or thread storage duration" というのは、
「静的記憶域期間またはスレッド記憶域期間を持つオブジェクト」であって、
「staticキーワードや _Thread_localキーワードを指定した場合のオブジェクト」
ということではありません。グローバル変数は、
static をつけると、静的記憶域期間で内部リンケージ、
static をつけないと、静的記憶域期間で外部リンケージになります。
したがって、グローバル変数は、static 指定がなくても、変数を使って初期化することはできません。
kaovines さんが書きました:引数int b_search(int x, int v[], int n)はこの表現のもとでどのようにしたらよいのかご教授お願いします。
再帰呼び出し版
コード:
int b_search(int x, int v[], int n)
{
int left = 0;
int right = n - 1;
if (left <= right) {
int m = (left + right) / 2;
if (x == v[m]) return m;
if (x < v[m]) right = m - 1;
else left = m + 1;
return left + b_search(x, v + left, right - left + 1);
}
return -1;
}
ループ版
コード:
int b_search(int x, int v[], int n)
{
int left = 0;
int right = n - 1;
while (left <= right) {
int m = (left + right) / 2;
if (x == v[m]) return m;
if (x < v[m]) right = m - 1;
else left = m + 1;
}
return -1;
}
どちらをご希望でしょうか？
Re: C言語 バイナリサーチについて
Posted: 2015年10月18日(日) 15:54
by kaovines
かずま さんが書きました:YuO さんが書きました:
ISO/IEC 9899:2011 / 6.7.9 Initializer / ¶4
All the expressions in an initializer for an object that has static or thread storage duration shall be constant expressions or string literals.
上記にあるように，staticや_Thread_localが特殊なのであって，そうでなければ，変数を使って初期化することも可能です。
その通りですが、念のため補足説明をしておきます。
"an object that has static or thread storage duration" というのは、
「静的記憶域期間またはスレッド記憶域期間を持つオブジェクト」であって、
「staticキーワードや _Thread_localキーワードを指定した場合のオブジェクト」
ということではありません。グローバル変数は、
static をつけると、静的記憶域期間で内部リンケージ、
static をつけないと、静的記憶域期間で外部リンケージになります。
したがって、グローバル変数は、static 指定がなくても、変数を使って初期化することはできません。
kaovines さんが書きました:引数int b_search(int x, int v[], int n)はこの表現のもとでどのようにしたらよいのかご教授お願いします。
再帰呼び出し版
コード:
int b_search(int x, int v[], int n)
{
int left = 0;
int right = n - 1;
if (left <= right) {
int m = (left + right) / 2;
if (x == v[m]) return m;
if (x < v[m]) right = m - 1;
else left = m + 1;
return left + b_search(x, v + left, right - left + 1);
}
return -1;
}
ループ版
コード:
int b_search(int x, int v[], int n)
{
int left = 0;
int right = n - 1;
while (left <= right) {
int m = (left + right) / 2;
if (x == v[m]) return m;
if (x < v[m]) right = m - 1;
else left = m + 1;
}
return -1;
}
どちらをご希望でしょうか？
まだ初心者なので詳しい仕様はわからないのですが、グローバル変数は、static 指定がなくても変数を使って初期化することはできないということは覚えておこうと思います。
b_search関数についても下請け関数なしに再帰できるようなので試してみます。
返信ありがとうございました。
Re: C言語 バイナリサーチについて
Posted: 2015年10月20日(火) 02:48
by かずま
存在しない場合、-1 を返す処理が抜けていました。
コード:
int b_search(int x, int v[], int n)
{
int left = 0, right = n - 1;
if (left <= right) {
int m = (left + right) / 2;
if (x == v[m]) return m;
if (x < v[m]) right = m - 1;
else left = m + 1;
m = b_search(x, v + left, right - left + 1);
return m == -1 ? -1 : left + m;
}
return -1;
}