在 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,
