【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.20296

2分探索について
投稿者---ポリンキー(2005/03/09 16:51:53)


ソートされたある数値の集まりに対して、2分探索により一度検索された数値を-1(仮)に書き換え、再度2分探索を行いたいのですが、良い方法はないでしょうか?
解決策として、リスト構造を使用するのが一番良いかと思うのですが、このような処理を2分探索で実現できるでしょうか?ご教授ください。

以下は普通の2分探索です。

/* nbuf:ソートされた数値の集まり, buf:検索する数値, len:数値の集まりの長さ */
int search(int nbuf[], int buf, int len)
{
 int low, high, mid;

 low = 0;
 high = len - 1;

 while(low <= high)
 {
  mid = (low + high) / 2;

  if(nbuf[mid]) < buf)
   low = mid + 1;
  else if(nbuf[mid] > buf)
   high = mid - 1;
  else
  {
   nbuf[mid] = -1; //一致したら-1へ変更
   return 0;
  }
 }
 return -1;
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:2分探索について 20297 おでん 2005/03/09 16:58:08
<子記事> Re:2分探索について 20306 秋嵩君 2005/03/09 19:00:52


No.20297

Re:2分探索について
投稿者---おでん(2005/03/09 16:58:08)


>ソートされたある数値の集まりに対して、2分探索により一度検索された数値を-1(仮)に書き換え、再度2分探索を行いたいのですが、良い方法はないでしょうか?
>解決策として、リスト構造を使用するのが一番良いかと思うのですが、このような処理を2分探索で実現できるでしょうか?ご教授ください。
>

リスト構造がいいと思った理由は何でしょう?
・・・項目数が固定ではないのでしょうか?

実現は可能ですが、−1を入れるたびにソートしなくては
ならないのは分かっていますか?


この投稿にコメントする

削除パスワード

No.20298

Re:2分探索について
投稿者---ポリンキー(2005/03/09 17:11:06)


ご解答有難うございます。


>リスト構造がいいと思った理由は何でしょう?
>・・・項目数が固定ではないのでしょうか?

すみません、言葉がたりませんでした。
リスト構造では、検索によりヒットした数値を-1ではなく
削除できるからという意味で記載させて頂きました。

>
>実現は可能ですが、−1を入れるたびにソートしなくては
>ならないのは分かっていますか?

やはり毎回ソートしなければならないのですか?
このような処理をできるだけ高速にするには、やはりリスト
構造を使用するしかないのでしょうか?





この投稿にコメントする

削除パスワード

No.20299

Re:2分探索について
投稿者---REE(2005/03/09 17:19:47)


>やはり毎回ソートしなければならないのですか?
>このような処理をできるだけ高速にするには、やはりリスト
>構造を使用するしかないのでしょうか?

そもそもリスト構造は、任意の要素に移動するためにリンクを辿る必要があるため、2分探索を高速に行うには向いていません。

要は検索するたびに要素を削除(または対象外に)することで、次回以降の検索時間を短縮したいということですよね?

ツリー構造にすれば、2分探索並みの速度で検索でき、且つ要素の削除も容易です。



この投稿にコメントする

削除パスワード

No.20301

Re:2分探索について
投稿者---ポリンキー(2005/03/09 17:27:58)


ご解答有難うございます。

>要は検索するたびに要素を削除(または対象外に)することで、次回以降の検索時間を短縮したいということですよね?

そうです。


>ツリー構造にすれば、2分探索並みの速度で検索でき、且つ要素の削除も容易です。

数値の集まりの初期状態がソートされた状態だとしても、ツリー構造が
有効になるのでしょうか?

ご教授ください。



この投稿にコメントする

削除パスワード

No.20302

Re:2分探索について
投稿者---あかま(2005/03/09 17:49:04)


>数値の集まりの初期状態がソートされた状態だとしても、ツリー構造が
>有効になるのでしょうか?
>
>ご教授ください。
AVL木やB木について調べると吉かも。



この投稿にコメントする

削除パスワード

No.20303

Re:2分探索について
投稿者---ポリンキー(2005/03/09 18:25:34)


ご解答有難うございました。

B木やAVL木を調べてみましたが、かなり複雑ですね。

いろいろ考えた結果、リスト構造を作成し、ハッシュ関数
を使用するという方法でいこうと思うのですが、如何でしょう?



この投稿にコメントする

削除パスワード

No.20304

Re:2分探索について
投稿者---REE(2005/03/09 18:42:32)


>いろいろ考えた結果、リスト構造を作成し、ハッシュ関数
>を使用するという方法でいこうと思うのですが、如何でしょう?

具体的な方法が分からないので、判断できませんが、
実際に作成して、試してみるのがよいでしょう。

その時には、もとの2分探索(-1に置き換える処理を無くしたもの)と比較するのを忘れずに(遅くなっていたら意味が無いので)



この投稿にコメントする

削除パスワード

No.20305

有難うございました
投稿者---ポリンキー(2005/03/09 18:51:36)


>その時には、もとの2分探索(-1に置き換える処理を無くしたもの)と比較するのを忘れずに(遅くなっていたら意味が無いので)

はい、わかりました。いろいろと有難うございました。



この投稿にコメントする

削除パスワード

No.20307

Re:有難うございました
投稿者---あかま(2005/03/09 19:37:52)


>>その時には、もとの2分探索(-1に置き換える処理を無くしたもの)と比較するのを忘れずに(遅くなっていたら意味が無いので)
>
>はい、わかりました。いろいろと有難うございました。

そういえば要素の数が十分に多ければ、探索した要素を削除しても探索時間はそうそう変わらないのでは?
要素数が半分になってやっと1回減るだけですし。
要素の数が少ないならそもそも削除しなければならないほど時間はかからないですし。


この投稿にコメントする

削除パスワード

No.20306

Re:2分探索について
投稿者---秋嵩君(2005/03/09 19:00:52)


検索対象が負数を含まないのなら、-1で置き換えるんじゃなくて、-1倍したもので置き換えればいいんじゃないですか。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧