続いて、二分探索を使ってみます。
Ｃ言語編でも作った「二分探索」も基本的なアルゴリズムとして用意されています。
今回も配列を使って実際のプログラムを作ってみましょう。
<sample program cpp024-01>
#include <iostream>
#include <algorithm>
int main()
{
const int COUNT = 10;
int data[COUNT];
for (int i = 0; i < COUNT; i++) {
data[i] = i * 10;
}
if (std::binary_search(data, &data[COUNT], 50)) {
std::cout << "Find" << std::endl;
}
else {
std::cout << "Not Found" << std::endl;
}
return 0;
}
|
<実行結果>
Find 続行するには何かキーを押してください・・・
binary_search関数の引数は、
std::binary_search(data, &data[COUNT], 50) |
「先頭アドレス」「最後のデータの次のアドレス」と「探したい値」です。
戻り値はbool型であり、発見した場合true、見つからなかった場合falseが返されます。
配列には０から１０刻みで９０まで格納してあります。
５０は必ずありますので、「Find」という結果が表示されています。
数値を変えれば結果も変わりますので、試してみてください。
ところで、二分探索を行うには条件がありましたよね？
データが「昇順」か「降順」に並んでいる事
これは非常に重要です。
ソートされていないデータを二分探索しても正しい答えは得られません。
しかし、標準テンプレートライブラリにはソート済みかどうか調べる関数も用意されています。
上のプログラムに追加してみましょう。
<sample program cpp024-02>
#include <iostream>
#include <algorithm>
int main()
{
const int COUNT = 10;
int data[COUNT];
for (int i = 0; i < COUNT; i++) {
data[i] = i * 10;
}
if (std::is_sorted(data, &data[COUNT])) {
std::cout << "Sorted" << std::endl;
}
else {
std::cout << "Not Sorted" << std::endl;
return 1;
}
if (std::binary_search(data, &data[COUNT], 50)) {
std::cout << "Find" << std::endl;
}
else {
std::cout << "Not Found" << std::endl;
}
return 0;
}
|
<実行結果>
Sorted Find 続行するには何かキーを押してください・・・
is_sorted関数を使えば、ソート済みであればtrueを返してくれます。
ただし、デフォルトは「昇順」にソート済みかどうかをチェックします。