在 C++ 中實現二叉搜尋
本文將解釋如何在 C++ 中實現二叉搜尋演算法。
在 C++ 中為 std::vector 容器實現二叉搜尋演算法
搜尋演算法是在大多數常見問題中使用的基本子程式，以最有效的方式執行它們很重要。有多種型別的搜尋演算法；有些是為特殊資料結構量身定製的，有些可以更普遍地應用。
二叉搜尋是一種分而治之的演算法，應該用於排序的鍵陣列。由於其最壞情況的效能，它通常被稱為對數搜尋，我們將在本文後面進行概述。
你可以將二叉搜尋描述為：一旦我們擁有需要找到 k 鍵的物件的排序陣列，我們應該將給定的鍵與陣列中的中間元素進行比較。如果鍵小於元素，它應該位於陣列的左半部分，或者如果它更大 - 我們應該在右半部分尋找它。
在我們對每個較小的半陣列遞迴重複這個查詢過程後，我們最終會找到鍵的位置或指示鍵不在陣列中。儘管我們將演算法描述為自然遞迴，但它可以使用迭代方法實現，但我們將重點介紹遞迴演算法。
以下示例程式碼生成 [1-1000] 範圍內的一千個隨機整數，並將它們儲存在 std::vector 容器中。然後使用 std::sort 演算法對向量進行排序，然後我們宣告另一個包含九個整數的向量進行搜尋。請注意，searchVector 包裝函式用於呼叫遞迴函式 binarySearch。
後者檢查兩個位置的第一個索引是否比另一個多；如果是，函式返回。返回值 -1 用於指示給定鍵的未找到狀態。接下來，計算中間位置並與鍵進行比較，如果為真則返回索引值。最後，我們選擇需要搜尋陣列的哪一部分，並使用相應的索引呼叫相同的函式。
#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,
