移动网站开发流行,常州网站制作多少钱,宜兴百度推广,北京营销型网站公司1 算法题 #xff1a;使用分块算法在有序数组中查找指定元素
1.1 题目含义
在给定一个有序数组的情况下#xff0c;使用分块查找算法来查找数组中是否包含指定的元素。分块查找算法是一种结合了顺序查找和二分查找思想的算法#xff0c;它将有序数组划分为若干个块#x…1 算法题 使用分块算法在有序数组中查找指定元素
1.1 题目含义
在给定一个有序数组的情况下使用分块查找算法来查找数组中是否包含指定的元素。分块查找算法是一种结合了顺序查找和二分查找思想的算法它将有序数组划分为若干个块每个块内的元素不必有序但块与块之间必须保持有序。首先通过块之间的有序性来快速定位到目标元素可能存在的块然后在该块内进行顺序查找。
1.2 示例
示例 1: 输入
有序数组[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]块大小5目标元素17
输出
7
说明
数组被划分为 3 个块[1, 3, 5, 7, 9]、[11, 13, 15, 17, 19] 和 [21, 23, 25, 27, 29]。通过比较块的首个元素可以确定目标元素 17 在第二个块中。然后在该块内进行顺序查找找到元素 17 的位置为 7从 0 开始计数。
示例 2: 输入
有序数组[1, 4, 6, 9, 13, 16, 19, 22, 25, 28]块大小4目标元素10
输出
-1
说明
数组被划分为 3 个块[1, 4, 6, 9]、[13, 16, 19, 22] 和 [25, 28]。通过比较块的首个元素可以确定目标元素 10 不在任何一个块中因此整个数组中也不存在该元素。
示例 3: 输入
有序数组[]块大小10目标元素50
输出
-1
说明
有序数组为空50 不存在于有序数组中返回 -1。
2 解题思路
2.1 简单分块查找
1确定块数
首先根据给定的块大小计算数组可以分成的块数。如果数组长度不是块大小的整数倍则最后一个块的大小可能会小于块大小。
2定位目标块
遍历数组中的块通过比较每个块的首个元素和目标元素的大小关系确定目标元素可能所在的块。如果目标元素小于当前块的首个元素则目标元素不可能在当前块及之后的块中可以提前结束遍历。
3块内顺序查找
在定位到的目标块内使用顺序查找算法来查找目标元素。从目标块的起始位置开始逐个比较元素直到找到目标元素或遍历完整个块。
4返回结果
如果找到了目标元素则返回其在数组中的位置索引。如果遍历完所有块都没有找到目标元素则返回表示未找到的标志如-1。
2.2 优化块内查找
这种思路在第一种的基础上对块内查找进行了优化。
1确定块数和索引映射
首先像第一种思路一样确定块数。然后可以建立一个索引映射关系将每个元素映射到其所属的块和块内的相对位置。这样可以在定位到目标块后直接计算出目标元素在块内的相对位置减少不必要的比较操作。
2定位目标块
这一步与第一种思路相同通过比较块的首个元素和目标元素的大小关系确定目标元素可能所在的块。
3块内直接定位
利用索引映射关系直接计算出目标元素在块内的相对位置。然后通过该相对位置访问数组元素检查是否为目标元素。
4返回结果
如果找到了目标元素则返回其在数组中的位置索引。如果遍历完所有块都没有找到目标元素则返回表示未找到的标志如-1。
3 算法实现代码
3.1 简单分块查找
如下为算法实现代码
#include iostream
#include vector
#include cmath
#include algorithm class Solution
{
public:// 分块查找算法实现 int blockSearch(const std::vectorint arr, int blockSize, int target) {int n arr.size();int blockNum (n blockSize - 1) / blockSize; // 计算块数向上取整 // 遍历块定位目标元素可能所在的块 for (int i 0; i blockNum; i) {int blockStart i * blockSize;int blockEnd std::min(blockStart blockSize, n); // 块内最后一个元素的索引 // 如果目标元素小于当前块的最小值则目标元素不可能在当前块及之后的块中 if (target arr[blockStart]) {break;}// 如果目标元素大于当前块的最大值则继续查找下一个块 if (target arr[blockEnd - 1]) {continue;}// 在目标块内进行顺序查找 for (int j blockStart; j blockEnd; j) {if (arr[j] target) {return j; // 返回目标元素在数组中的位置 }}}return -1; // 未找到目标元素 }
};这段代码首先计算了块数 blockNum然后遍历每个块通过比较块的首个元素 arr[blockStart] 和最后一个元素 arr[blockEnd - 1] 与目标元素 target 的大小关系来确定目标元素可能所在的块。如果目标元素小于当前块的最小值则它不可能在当前块及之后的块中可以提前结束遍历。如果目标元素在当前块内则在该块内进行顺序查找直到找到目标元素或遍历完整个块。如果遍历完所有块都没有找到目标元素则返回 -1 表示未找到。
调用上面的算法并得到输出
int main()
{Solution s;std::vectorint arr { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 };int blockSize 5; // 块大小 int target 17; // 目标元素 int index s.blockSearch(arr, blockSize, target);if (index ! -1) {std::cout Element found at index: index std::endl;}else {std::cout Element not found in the array. std::endl;}return 0;
}上面代码的输出为
Element found at index: 83.2 优化块内查找
如下为算法实现代码
#include iostream
#include vector
#include cmath
#include algorithm
#include unordered_map class Solution
{
public:// 分块查找算法实现 int blockSearch(const std::vectorint arr, int blockSize, int target) {int n arr.size();int blockNum (n blockSize - 1) / blockSize; // 计算块数向上取整 std::unordered_mapint, std::pairint, int blockIndicesAndOffsets; // 存储块索引和块内偏移量 computeBlockIndicesAndOffsets(arr, blockSize, blockIndicesAndOffsets);// 遍历块定位目标元素可能所在的块 for (int i 0; i blockNum; i) {int blockStart i * blockSize;int blockEnd std::min(blockStart blockSize, n); // 块内最后一个元素的索引 // 如果目标元素小于当前块的最小值则目标元素不可能在当前块及之后的块中 if (target arr[blockStart]) {break;}// 如果目标元素大于当前块的最大值则继续查找下一个块 if (target arr[blockEnd - 1]) {continue;}// 检查目标元素是否在块内并返回其位置 auto it blockIndicesAndOffsets.find(target);if (it ! blockIndicesAndOffsets.end() it-second.first i) {return blockStart it-second.second; // 返回目标元素在数组中的位置 }}return -1; // 未找到目标元素 }private:// 计算并存储每个元素的块索引和块内偏移量 void computeBlockIndicesAndOffsets(const std::vectorint arr, int blockSize,std::unordered_mapint, std::pairint, int blockIndicesAndOffsets) {int n arr.size();for (int i 0; i n; i) {int blockIndex i / blockSize;int offset i % blockSize;blockIndicesAndOffsets[arr[i]] { blockIndex, offset };}}
};在这个代码中computeBlockIndicesAndOffsets 函数用于计算并存储每个元素的块索引和块内偏移量。optimizedBlockSearch 函数首先通过遍历块来定位目标元素可能所在的块然后直接检查目标元素是否在预计算的块索引和偏移量映射中并且其块索引与当前遍历的块索引相匹配。如果找到匹配项则直接返回目标元素在数组中的位置。
注意这种方法只适用于数组不会改变的情况因为一旦数组发生变化就需要重新计算块索引和偏移量。此外如果数组非常大或者元素非常多存储块索引和偏移量映射可能会消耗大量内存。因此在实际应用中需要根据具体情况权衡这种优化方法的利弊。
4 测试用例
以下是针对上面算法的测试用例基本覆盖了各种情况
1基础测试用例 输入数组 arr {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}块大小 blockSize 5目标元素 target 17 输出找到目标元素 17位置为 8 说明目标元素位于第三个块内算法能够正确找到其位置。
2边界测试用例 输入数组 arr {1, 3, 5, 7, 9}块大小 blockSize 3目标元素 target 1 输出找到目标元素 1位置为 0 说明目标元素位于数组的第一个元素算法能够正确处理边界情况。
输入数组 arr {1, 3, 5, 7, 9}块大小 blockSize 3目标元素 target 9 输出找到目标元素 9位置为 4 说明目标元素位于数组的最后一个元素算法能够正确处理边界情况。
3块内查找测试用例 输入数组 arr {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}块大小 blockSize 5目标元素 target 23 输出找到目标元素 23位置为 12 说明目标元素位于第三个块内但不是块的首个或末尾元素算法能够在块内正确找到目标元素。
4未找到目标元素测试用例 输入数组 arr {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}块大小 blockSize 5目标元素 target 30 输出未找到目标元素 30 说明目标元素不在数组中算法能够正确处理未找到目标元素的情况。
5空数组测试用例 输入数组 arr {}块大小 blockSize 5目标元素 target 1 输出未找到目标元素 1 说明数组为空算法能够正确处理空数组的情况。
6单个块测试用例 输入数组 arr {1, 2, 3, 4, 5}块大小 blockSize 5目标元素 target 3 输出找到目标元素 3位置为 2 说明整个数组只包含一个块算法能够正确处理单个块的情况。
