在 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::vector;
using std::endl;
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::vector;
using std::endl;
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,
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn