C++ 常用查找算法有哪些
当涉及查找算法时，C++中常用的查找算法大致可以分为两类：顺序查找和二分查找。让我逐一为您详细解释：
- 线性查找（Linear Search）：
- 概念：线性查找是最简单的一种查找算法，也称为顺序查找。它是通过顺序比较数据元素，逐个地检查目标值是否与当前元素相等，直到找到目标值或搜索完整个数组。
- 原理：从数组的第一个元素开始，逐个与目标值比较，直到找到目标值或搜索完整个数组。
- 二分查找（Binary Search）：
- 概念：二分查找是一种高效的查找算法，前提是数组已排序。通过不断将搜索区间对半分割，缩小搜索范围直至找到目标值。
- 原理：首先确定数组的中点，然后将目标值与中点值进行比较。如果目标值等于中点值，则找到；如果小于中点值，则在左半边继续查找；如果大于中点值，则在右半边继续查找。重复以上步骤直到找到目标值或确定目标值不存在。
- 插值查找（Interpolation Search）：
- 概念：插值查找是一种改进的二分查找算法，根据目标值在已排序数组中的大致位置进行估计，以减少查找次数。
- 原理：根据目标值与首尾元素的关系，估计目标值在数组中的大致位置，然后通过区间划分类似于二分查找来寻找目标值。
- 斐波那契查找（Fibonacci Search）：
- 概念：斐波那契查找利用黄金分割比例进行查找，相对于二分查找，避免每次将数组对半分。
- 原理：根据斐波那契数列产生的黄金分割点，确定搜索位置，然后继续类似二分查找的操作。
- 二叉搜索树（Binary Search Tree）：
- 概念：二叉搜索树是一种基于二叉树结构的查找算法，左子树的所有节点值均小于根节点值，右子树的所有节点值均大于根节点值。
- 原理：根据当前节点值与目标值的大小关系，在左子树或右子树中递归查找目标值。
- 平衡二叉树（Balanced Binary Tree）：
- 概念：平衡二叉搜索树是一种特殊的二叉搜索树，保持树的平衡，如AVL树、红黑树等。
- 原理：通过旋转操作保持树的平衡，以确保查找、插入和删除的平均时间复杂度为O(log n)。
- 哈希表（Hash Table）：
- 概念：哈希表利用哈希函数将关键字映射到表中的位置，实现高效的查找操作。
- 原理：通过哈希函数计算关键字的哈希值，然后将其存储在哈希表中对应的位置。在查找时，通过哈希函数计算出目标值的位置，并在该位置进行查找。
以上是C++中常见的查找算法的详细概念和原理，每种算法有其适用场景和优劣势，根据具体情况选择合适的查找算法可以提高算法的效率。
下面要讲的和上面算法有一定的关系，可以理解为就是上边算法在方法中的应用。
常用查找算法-find if
在C++标准库中，有一个常用的查找算法叫做find_if，该算法用于在指定范围内查找满足指定条件的第一个元素。下面我会详细介绍一下find_if算法的概念和用法：
find_if算法：
- 概念：
find_if算法用于在指定范围内查找第一个满足特定条件的元素，它接受两个迭代器作为参数表示查找范围，并接受一个谓词（函数对象或lambda表达式）作为判断条件。 - 原理：
find_if算法从指定范围的起始位置开始逐个检查元素，直到找到第一个使得条件函数返回true的元素或者遍历完整个范围。 - 用法：
find_if函数的使用方式如下所示：
template< class InputIt, class UnaryPredicate > InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );
first：指向要搜索的范围的起始位置的迭代器last：指向要搜索的范围的末尾之后位置的迭代器p：用于判断条件的函数对象或lambda表达式
- 示例：假设有一个存储整数的容器
vector<int> vec，我们想查找第一个大于10的元素，可以使用find_if算法：
auto it = std::find_if(vec.begin(), vec.end(), [](int x){ return x > 10; }); if (it != vec.end()) { std::cout << "找到第一个大于10的元素：" << *it << std::endl; } else { std::cout << "未找到满足条件的元素" << std::endl; }
通过find_if算法，可以方便地在容器或数组等序列容器中查找满足特定条件的第一个元素，具有很好的灵活性和可扩展性。
常用查找算法-adjacent find
std::adjacent_find 是 C++ 标准库中的一个常用查找算法，用于在指定范围内查找相邻重复元素的第一个位置。下面我将详细介绍 std::adjacent_find 算法的概念和用法：
adjacent_find算法：
- 概念：
std::adjacent_find用于在指定范围内查找第一对相邻重复的元素，即两个相邻且相等的元素。该算法接受两个迭代器表示查找范围。 - 原理：
std::adjacent_find会从指定范围的起始位置开始逐对检查元素，直到找到第一对相邻重复的元素或者遍历完整个范围。 - 用法：
std::adjacent_find函数的使用方式如下所示：
template<class ForwardIt> ForwardIt adjacent_find(ForwardIt first, ForwardIt last);
first：指向要搜索的范围的起始位置的迭代器last：指向要搜索的范围的末尾之后位置的迭代器
- 示例：假设有一个存储整数的容器
std::vector<int> vec，我们想查找第一对相邻重复的元素，可以使用std::adjacent_find算法：
auto it = std::adjacent_find(vec.begin(), vec.end()); if (it != vec.end()) { std::cout << "找到第一对相邻重复的元素：" << *it << std::endl; } else { std::cout << "未找到相邻重复元素" << std::endl; }
通过 std::adjacent_find 算法，可以快速找到指定范围内第一对相邻重复的元素，并进行相应的处理。这个算法在某些情况下非常实用，帮助我们高效地处理数据中的重复情况。
常用查找算法-binary search
std::binary_search 是 C++ 标准库中的一个常用的查找算法，用于在已经排序好的序列（如数组或容器）中进行二分查找。下面我将详细介绍 std::binary_search 算法的概念和用法：
binary_search算法：
- 概念：
std::binary_search用于在已排序的序列中进行二分查找，判断某个值是否存在于序列中。该算法接受两个迭代器表示排序好的序列和要查找的值。 - 注意：在应用
std::binary_search前，需要确保序列是按照升序排列的，否则结果会不准确。 - 用法：
std::binary_search函数的使用方式如下所示：
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );
first：指向排序好的序列的起始位置的迭代器last：指向排序好的序列的末尾位置的下一个迭代器value：要查找的值
- 示例：假设有一个按升序排列的整数数组
int arr[] = {1, 3, 5, 7, 9};，我们想要查找是否存在值为5的元素，可以使用std::binary_search算法：
int key = 5; if (std::binary_search(arr, arr + 5, key)) { std::cout << "值为" << key << "的元素在数组中找到了" << std::endl; } else { std::cout << "值为" << key << "的元素在数组中未找到" << std::endl; }
通过 std::binary_search 算法，可以高效地在已排序的序列中进行查找操作，如果找到了指定的值，则返回true，否则返回false。这个算法利用二分查找的思想，具有较高的查找效率。
常用查找算法-count
std::count 是 C++ 标准库中的一个常用查找算法，用于计算指定范围内等于给定值的元素数量。下面我将详细介绍 std::count 算法的概念和用法：
count算法：
- 概念：
std::count用于在指定范围内计算等于给定值的元素的数量。该算法接受两个迭代器表示搜索范围，并接受一个要计数的值。 - 用法：
std::count函数的使用方式如下所示：
template< class InputIt, class T > typename iterator_traits<InputIt>::difference_type count( InputIt first, InputIt last, const T& value );
first：指向要搜索的范围的起始位置的迭代器last：指向要搜索的范围的末尾位置的下一个迭代器value：要计数的值
- 示例：假设有一个存储整数的容器
std::vector<int> vec {1, 2, 3, 4, 5, 3, 3, 6};，我们想计算值为3的元素的数量，可以使用std::count算法：
int count = std::count(vec.begin(), vec.end(), 3); std::cout << "值为3的元素数量为：" << count << std::endl;
通过 std::count 算法，可以方便地计算指定范围内等于给定值的元素的数量。
常用查找算法-count if
std::count_if 是 C++ 标准库中的一个常用的查找算法，用于计算满足指定条件的元素数量。下面是关于 std::count_if 算法的详细介绍：
count_if算法：
- 概念：
std::count_if用于在指定范围内计算满足给定条件的元素数量。该算法接受两个迭代器表示搜索范围，并接受一个谓词（predicate）函数来判断元素是否满足条件。 - 用法：
std::count_if函数的使用方式如下所示：
template< class InputIt, class UnaryPredicate > typename iterator_traits<InputIt>::difference_type count_if( InputIt first, InputIt last, UnaryPredicate p );
first：指向要搜索的范围的起始位置的迭代器last：指向要搜索的范围的末尾位置的下一个迭代器p：谓词函数，用于定义判断条件的函数对象
- 示例：假设有一个存储整数的容器
std::vector<int> vec {1, 2, 3, 4, 5, 3, 3, 6};，我们想计算大于等于3的元素的数量，可以使用std::count_if算法：
int count = std::count_if(vec.begin(), vec.end(), [](int num){ return num >= 3; }); std::cout << "大于等于3的元素数量为：" << count << std::endl;
通过这段代码，我们利用 lambda 表达式作为谓词来判断元素是否大于等于 3，然后使用 std::count_if 算法来计算满足条件的元素数量。这就是 std::count_if 算法的基本用法，对于复杂的条件判断，可以编写相应的谓词函数来传递给 count_if 算法。
关注我，不迷路，共学习，同进步
感谢大家，我一直在努力…
