• ベストアンサー

二分探索アルゴリズムの終了条件について

soakunの回答

  • soakun
  • ベストアンサー率66% (6/9)
回答No.3

>ところでsoakunさんのプログラムに誤りらしきものが・・(^^; あぅ、どこが間違いなのでしょう?(^^; # もしかしたらここを見る人のためにも修正したいので補足よろしゅー

aaaaa
質問者

補足

はい。入力ミスっぽいのとうっかりミスっぽいのがありました。 (1)while(l > h)    これの符号は逆ですよね。 (2)while(・・){     if(array[t] == mokuteki)       break;    }    return (l > h) ? t : (-1);    目的値が見つかっても負を返しちゃいますよね。    間違ってたらごめんなさいです。(~~)/~

関連するQ&A

  • アルゴリズム(2分探索木)の問題について

    2分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 1.vの左部分木の頂点uに対して l(u) < l(v) 2.vの右部分木の頂点uに対して l(u) > l(v) 3.Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。

  • 二分探索木のheightを見つけるアルゴリズム2

    誠に申し訳ありません。 前回下記のとおり質問して、 二分探索木のheight(高さ?)を見つけるアルゴリズム http://www.okweb.ne.jp/kotaeru.php3?q=710354 丁寧な回答を頂き、自分では解決したと思い、 お礼も差し上げたのですが 私のメソッドは正しく動いていないようです。 どうやら私が間違って解釈してしまったようです。 public int height() { return height(root, 0); } public int height(IntBSTNode p, int h) { if (p != null && p.right != null && p.left != null) { if (p.left.key < p.right.key) return height(p.right, h+1); else return height(p.left, h+1); } return h; } 何を思ったのか、 if (p.left.key < p.right.key)では 左と右の「値」を比較しています。 なので入力した値によって「たまたま」動いてました。 本当は左と右の「height」を比較しなければならなかったのに…。 if (p != null && p.right != null && p.left != null)の条件もこれでいいのか…。 いろいろやってみたのですが行き詰まりました。 どうか、更にヒントを下さい。お願いします。

    • ベストアンサー
    • Java
  • アルゴリズムの正当性について

    線形探索法のアルゴリズムの擬似コードを書いて、そのアルゴリズムの正当性をループ不変式を用いて証明するという課題があります。 擬似コードは以下のような流れにしようと思いますが、この場合成り立つループ不変はどのようなことになりますか? 配列A[a1..an]に対してv=A[i]ならば添字iを、vがAの中になければNILを出力するアルゴリズムです。 for i ←1 to N if A[i] = v return i return NIL

  • アルゴリズム:2分探索の時間計算量

    アルゴリズムの参考書を読んでいて疑問に思ったんですが、教えてください。 /* 2分探索 */ #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を2分探索 ---*/ int bin_search(const int a[], int n, int key) { int pl = 0;/* 探索範囲先頭の添字【1】 */ int pr = n-1;/* 〃  末尾の添字 【2】*/ int pc; /*   〃  中央の添字 */ do { pc = (pl + pr) / 2;/*【3】*/ if (a[pc] == key) /* 探索成功【4】 */ return (pc);/*【5】*/ else if (a[pc] < key)/*【6】*/ pl = pc + 1;/*【7】*/ else /*【8】*/ pr = pc - 1;/*【9】*/ } while (pl <= pr);/*【10】*/ return (-1);/* 探索失敗【11】 */ } のプログラムがありますが、【1】から【11】までの 実行回数と計算量は次のようになるそうですが、    実行回数   計算量  【1】  1       O(1) 【2】  1       O(1) 【3】  logn     O(logn) 【4】  logn     O(logn) 【5】  1       O(1) 【6】  logn     O(logn) 【7】  logn     O(logn) 【8】  logn     O(logn) 【9】  logn     O(logn) 【10】  logn     O(logn) 【11】  1       O(1) なぜ【3】や【4】がlognになるんでしょうか? 詳しく教えてください。 よろしくお願いします。

  • 線形探索と二分探索

    線形探索と二分探索のプログラムを作成中です。 自力(本やwebに落ちているサンプルを参考にして)でここまで作りましたが正直自信がありません。どうかお願いします。 #include <stdio.h> #define ARRAYI1_MAX sizeof(array1) #define ARRAYI2_MAX sizeof(array2) //int binary_search(int*,int,int); //二分探索関数のプロトタイプ宣言 int liner_search(int*,int,int); //線形探索関数のプロトタイプ宣言 void main(void) { int array1[]={2,3,5,8,12,20,32,52}; int array2[]={22,34,65,66,12,33,43,5,1}; int result,key; printf("探す文字を入力して下さい。\n"); sacnf("%d",&key); result=liner_search(array1,ARRAYI1_MAX,key); if(result<0){ printf("見つかりませんでした\n");} else{ printf("%d番目に見つかりました\n",result);} } //線形探索 int liner_search(int*array,int num_array,int key) { int i=0; for(i=0;i<result;i++) } /*二分探索 int binary_search(int*array,int num_array,int key) { }*/

  • C言語の二分探索法について質問です。

    C言語の2分探索法について質問です。 以下のようなプログラムを作りたいのですが,途中でよく分からなくなってしまいました。添削お願いします。 入力された整数を配列に順次格納する(必ず昇順になるように入力)。0が入力された時に整数の入力を終了し, 次に入力された数字を二分探索によって配列から探索し,その配列の添字番号を出力するプログラムを作成せよ。 実行例 (例1) (例2) 9 ←入力 1 ←入力 7 ←入力 42 ←入力 69 ←入力 99 ←入力 31 ←入力 13 ←入力 93 ←入力 0 ←入力 59 ←入力 5 ←入力 17 ←入力 not found ←出力 0 ←入力 7 ←入力 2 ←出力 プログラム #include <stdio.h> #include <stdlib.h> #define ARRAY_SIZE 10 int swap(int a, int b) { int c; c = a; a = b; b = a; } int main(void) { int array[] ; int low = 0; int high = n - 1; int mid; int key; int i, j, n; int data; struct node *p; puts("整数を入力して下さい。"); for(i = 0; i < ARRAY_SIZE && scanf("%d", array + i) == 1; ++i){ if(array[i] == 0) break; for(j = i; j > 0 && array[j-1] > array[j]; j--) swap(array[j-1], array[j]); } n = i; puts( "探索する値を入力して下さい" ); scanf( "%d", &key ); while( low <= high ) / { mid = (low + high) / 2; if( array[mid] == key ) { return ; } else if( array[mid] < key ) { low = mid + 1; } else { high = mid - 1; } } puts( "not found" ); return 0; }

  • BMサーチというアルゴリズム

    昔、CマガジンでBMサーチという文字列を早く検索するアルゴリズムがあったのですが、その本がなく、詳しいソースや解説をしているサイトや本を探しています。 moto = "....."; if ( strcmp(moto, "AA") == 0 ) { }else if ( strcmp(moto, "AB") == 0 ) { ... } と、BMサーチではどちらが早いのでしょうか? Cライブラリになっているので、中でBMサーチみたいなことはしているのでしょうか?

  • 多分探索木の昇順出力

    多分探索木の昇順出力する。関数を作っています。以下の関数が、多分木を出力関数ですが 途中でセグメントエラーが起きてしまいます。 void out_MS(NODE *p){ int i,n=0 ; for(i = 0; i <= p->nkeys; ++i) if (p->refs[i] != NULL) out_MS(p->refs[i]) ; while(p->keys[n+1]!='\0'){ printf("No:%3d \"%s\"\n",count,p->keys[n]) ; count++; n++; } } この、多分木に使われている、構造体は以下のとおりです #define KK 16 typedef struct node{ // 多分探索木、B(B*)木構造体 char *keys[KK] ; // キー配列 int nkeys ; // キーの個数(実際の) struct node *refs[KK + 1] ; // 子への参照欄 } NODE ; この構造体に以下の関数で、10万要素の単語(ランダム)に追加していきます。 int add(NODE *root, char *inv) { NODE *now , // 当該節 *prnt ; // nowの親節 int pos ; // 節内のキーの追加位置 prnt = now = root ; while(now != NULL) { // キーの探索 pos = binsearch(now->keys, now->nkeys, inv) ; // 二分探索 if (pos < now->nkeys && strcmp(inv,now->keys[pos])==0) // 探索値はある return FLS ; // 追加の必要なし if (now->nkeys == KK) { // 当該節に無い、節内に空きが無い prnt = now ; now = now->refs[pos] ; // 子の節へ }else if (pos <= now->nkeys) // 当該節に無い-追加位置が範囲内 break ; } if (now != NULL) // 当該節は在る store_key(now, inv, pos, &(now->nkeys)) ; // 当該節にキーを追加格納 else { // 当該節は無い-新規生成 if (now != root) { // nowは根ではない now = set_key(KK, inv) ; // キーを新節に格納 prnt->refs[pos] = now ; // 親節の参照欄に新節の番地を格納 }else return FLS ; } return 1 ; } 上記の関数で使われている、store_key set_key binserch の関数は以下のとおりです void store_key(NODE *trgt, char *inv, int pos, int *nkeys) { if (trgt->keys[pos] == INTV) // 当該位置は空 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 else { // 当該位置に入っている shift_element(trgt, 'R', pos, *nkeys) ; // 要素を移動 trgt->keys[pos] = strdup(inv) ; // 当該位置に格納 } ++*nkeys ; return ; } int binsearch(char *array[], int size, char *inv){ // 二分探索 int mid, // 当該位置 low, // 探索範囲の下限 high ; // 探索範囲の下限 if (size == 0) // キーは格納されていない return 0 ; if (strcmp(inv,array[0])<0) // 探索範囲以下 return 0 ; if (0 < strcmp(inv,array[size - 1] )) // 探索範囲以上 return size ; low = 0 ; // 下限設定 high= size - 1 ; // 上限設定 while(0 <= high - low) { // 二分探索本体 mid = (high + low) >> 1 ; // 中間位置を調べる if (strcmp(inv,array[mid])==0) // 入力値が一致したとき return mid ; if (strcmp(inv,array[mid])<0) // 入力値が小さいとき high = mid - 1; else // 入力値が大きいとき low = mid + 1 ; } return low ; } NODE *set_key(int size, char *key) { NODE *new ; new = crt_node(size) ; // 節の生成 new->keys[0] = strdup(key) ; // 配列の先頭に入力値を格納 new->nkeys = 1 ; // 節内の実際の要素数 return new ; } ぜひ、お力をお貸しください。よろしくお願いします。

  • JAVAの配列関連

    java の配列について質問があります。 わかりそうでわからない、というところであります。 【質問】 以下のような要素数の不明な配列を1つの文字列にする場合 どの様に処理したら良いのでしょうか。 ただし、array には何らかの文字列が既に入っているとします。 (どのように for 文などでくくれば、上手く出来るでしょうか。) ArrayList<String> array = new ArrayList<String>(); int size = array.size(); String str = null; if(size == 0){    str = (array.get(0)); } else if(size == 1){    str = (array.get(0) + "," + array.get(1)); } else if(size == 2){    str = (array.get(0) + "," + array.get(1) + "," + array.get(2)); } else if(size == 3){    str = (array.get(0) + "," + array.get(1) + "," + array.get(2) + "," + array.get(3)); } else if(size == 4){    str = (array.get(0) + "," + array.get(1) + "," + array.get(2) + "," + array.get(3) + "," + array.get(4)); }・・・ この if文 の部分を for文 ですっきりさせたいのですが どうにも思いつきません。 ご存知の方いらっしゃいましたら お力添えをお願いいたします。

    • ベストアンサー
    • Java
  • アルゴリズム・ネストループ方式って何?

    プログラムの性能改善の課題が出ているのですが、アルゴリズムとしてネストループ方式、もしくはその延長上のものを用いること、とあります。 図書館でアルゴリズム関係の本を見てみたのですがどこにもネストループに関して説明がなく、大変困っています。 プログラム自体は、ファイルを読み込んで、表示させるだけの簡単なものです。 簡単に抜き出すと、 for (i=0;; i++){ if ((st = read_a(fd_name, &name_buf, i)) <=0) break; for (j = 0;; j++){ if ((st =read_a (fd_home,&home_buf ,j)) <= 0) break; if (!strcmp(name_buf.a , home_buf.b)){ printf("%s =%s (%s)\n", name_buf.a, name_buf.c , home_buf.c); } } if (st <0) break; といったものです。 注意事項として、break文を入れる手法を使わないこととあります。 お願いします。ネストループって何でしょう?教えてください。