二分探索について質問です。

Question

見て頂きありがとうございます。質問です。

例えば配列の中に0から始まり+1ずつ昇順で数値が入っているとします。
arry[10] = {0,1,2,3,4,....};（今は１０の配列ですが実際は１０万とか膨大な数だと思ってください。）

これで７を探索するとかは解るんです。

ここで疑問に思ったんですが、例えば
array[10] = {3,1,5,6,2,4...};

こういう風にランダムで数値が入っていた時に、
目的の値を取り出すときは皆さんはどう探索しているのでしょうか？

私の考えではクイックソートとかで昇順にしてから二分探索でもするのかな？と思っているのですが。

時間あれば返答よろしくお願いします。

Answer 1

クイックソート（O(n log n)）は線形探索（O(n)）よりも遅いので、

• 探索するのが一度か数回だけなら線形探索
• 何度も探索するならクイックソートして二分探索

と使い分けますかね。

Comments

[nyan_lia]

なるほど、そういう風に使い分けしていくのですね。

回答ありがとうございました。

Answer 2

ソートをするってことは、各要素を１回はアクセスするんですよね。
それなら、なにも考えずに頭から最後まで順番にアクセスして、目的の数字の存在をチェックすればよいのでは？
ソートしてから二分探索するよりは速いはず...

Answer 3

二分探査はソートしてあることが前提の探査法なので、ばらばらの配列に対して二分探査しても意味はありません。
ソートしてから二分探査することになります。ソート方法はクイックソートでもマージソートでも好きなものを使えばいいのではないでしょうか。

Comments

[nyan_lia]

そうですねそもそも二分探索ってソートしてあることが前提なんですね。
ソートは下に書かれてあるOdacchiさんの複合ソートでいこうかなぁって思ってます。

回答ありがとうございます。

Answer 4

2分探索は、ソート済み配列に対する探索アルゴリズムですので、
その考えは正しいです。

（一応ソートについて補足ですが、多くの言語で提供されている標準的なソートアルゴリズムは、クイックソートではあるのですが、実際は、クイックソートはソート処理の前のオーバーヘッドが大きいので、要素数が一定数以下になると挿入ソートに切り替える、クイックソート＋挿入ソートの複合ソートだったりします。）

Comments

[nyan_lia]

考えが正しくてよかったです。

回答ありがとうございました。

Answer 5

こんにちは。

私は、要素を登録する際に2分探索で昇順に並べておいて、2分探索でサーチすることが多いです。
C++でプログラムすることがほとんどなのですが、最近std::mapの使い方を悟ったので、寿命が短いものならstd::mapで赤黒木にしてます。

Comments

[nyan_lia]

やっぱりあらかじめ昇順で並べておいた方が楽なんですね。
赤黒木は二分探索木のようなものなんですかね？
ちょっとアルゴリズム調べてみます。

回答ありがとうございました。