突破编程_C++_查找算法（分块查找）

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::vector<int>& 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::vector<int> 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: 8

3.2 优化块内查找

如下为算法实现代码：

#include <iostream>  
#include <vector>  
#include <cmath>  
#include <algorithm>  
#include <unordered_map>  class Solution
{
public:// 分块查找算法实现  int blockSearch(const std::vector<int>& arr, int blockSize, int target) {int n = arr.size();int blockNum = (n + blockSize - 1) / blockSize; // 计算块数，向上取整  std::unordered_map<int, std::pair<int, 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::vector<int>& arr, int blockSize,std::unordered_map<int, std::pair<int, 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
说明：整个数组只包含一个块，算法能够正确处理单个块的情况。