C++ でバイナリ検索を実装する
この記事では、C++ でバイナリ検索アルゴリズムを実装する方法について説明します。
C++ で std::vector コンテナのバイナリ検索アルゴリズムを実装する
検索アルゴリズムは、最も一般的な問題で使用される基本的なサブルーチンであり、最も効率的な方法でそれらを実行することが重要です。検索アルゴリズムにはさまざまな種類があります。特別なデータ構造に合わせて調整されたものもあれば、より一般的に適用できるものもあります。
二分探索は分割統治型のアルゴリズムであり、ソートされたキーの配列で使用する必要があります。パフォーマンスが最悪の場合、対数探索と呼ばれることがよくあります。これについては、この記事の後半で概説します。
バイナリ検索は次のように説明できます。k キーを見つける必要があるオブジェクトの並べ替えられた配列を取得したら、指定されたキーを配列の中央の要素と比較する必要があります。キーが要素よりも小さい場合は、配列の左半分に配置する必要があります。それよりも大きい場合は、右半分でキーを探す必要があります。
小さいハーフ配列ごとにこのルックアッププロセスを再帰的に繰り返した後、最終的にキーの位置を見つけるか、キーが配列内にないことを示します。アルゴリズムを自然再帰として説明しますが、反復法を使用して実装できますが、ここでは再帰的な方法に焦点を当てます。
次のサンプルコードは、[1-1000] の範囲で 1000 個のランダムな整数を生成し、それらを std::vector コンテナに格納します。次に、ベクトルは std::sort アルゴリズムを使用してソートされ、検索する 9つの整数の別のベクトルを宣言します。searchVector ラッパー関数は、再帰関数 binarySearch を呼び出すために使用されることに注意してください。
後者は、2つの位置のインデックスからの最初のものが他のものよりも多いかどうかをチェックします。その場合、関数は戻ります。戻り値 -1 は、指定されたキーの見つからないステータスを示すために使用されます。次に、中央の位置が計算され、キーと比較されます。キーは、true の場合にインデックス値を返します。最後に、配列のどの部分を検索する必要があるかを選択し、対応するインデックスを使用して同じ関数を呼び出します。
#include <iostream>
#include <random>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;
template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
if (s1 > s2) return -1;
auto middle = (s1 + s2) / 2;
if (item == vec.at(middle)) return middle;
if (item > vec.at(middle))
return binarySearch(vec, item, middle + 1, s2);
else
return binarySearch(vec, item, s1, middle - 1);
}
template <typename T>
int searchVector(const vector<T> &vec, T &item) {
return binarySearch(vec, item, 0, vec.size() - 1);
}
int main() {
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
std::vector<int> vec;
vec.reserve(NUMS_TO_GEN);
for (int n = 0; n < NUMS_TO_GEN; ++n) {
vec.push_back(distr(eng));
}
std::sort(vec.begin(), vec.end());
std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
for (auto &item : vec2) {
searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
}
cout << endl;
return EXIT_SUCCESS;
}
出力：
did not, found, found, did not, found, did not, found, did not, found,
二分探索アルゴリズムの複雑さの分析
二分探索は O(log n) の複雑さを持っているため、別名は対数探索です。再帰コストを分析することにより、再帰アルゴリズム実装の実行時間を大まかに見積もることができます。中央の要素を検索することは定数時間の操作であり、配列の半分をトラバースする必要があることに注意してください。
次のプログラムでは、STL std::sort アルゴリズムを使用したバイナリ検索関数の検証テストを示します。ただし、このチェックはフォーマル検証ではなく、コードの動作をデバッグおよび分析するためのアルゴリズム実装プロセス中の高速テストケースを提供するだけであることに注意してください。
#include <iostream>
#include <random>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;
template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
if (s1 > s2) return -1;
auto middle = (s1 + s2) / 2;
if (item == vec.at(middle)) return middle;
if (item > vec.at(middle))
return binarySearch(vec, item, middle + 1, s2);
else
return binarySearch(vec, item, s1, middle - 1);
}
template <typename T>
int searchVector(const vector<T> &vec, T &item) {
return binarySearch(vec, item, 0, vec.size() - 1);
}
int main() {
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
std::vector<int> vec;
vec.reserve(NUMS_TO_GEN);
for (int n = 0; n < NUMS_TO_GEN; ++n) {
vec.push_back(distr(eng));
}
std::sort(vec.begin(), vec.end());
std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
for (auto &item : vec2) {
searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
}
cout << endl;
for (auto &item : vec2) {
std::find(vec.begin(), vec.end(), item) != vec.end() ? cout << "found, "
: cout << "did not, ";
}
return EXIT_SUCCESS;
}
出力：
found, found, found, found, did not, did not, found, found, found,
found, found, found, found, did not, did not, found, found, found,
