c++二维数组二分查找通用函数

在C++中，二分查找通常用于一维有序数组，但对于二维数组，由于它是矩阵形式的数据结构，我们一般不会直接应用二分查找。因为二分查找依赖于元素的线性排列，而二维数组的索引通常是行优先（i, j）或列优先（j, i）。不过，如果你有一个预处理好的二维有序数组，并且想要查找特定值对应的位置，可以将其视为一维化后进行操作。 以下是一个简单的例子，假设我们要在一维化后的二维数组上进行二分查找： ```cpp #include <vector> #include <iostream> // 二维数组转换为一维 std::pair<int, int> flatten(const std::vector<std::vector<int>>& matrix, int value) { std::vector<int> flat; for (const auto& row : matrix) { for (int elem : row) { if (elem == value) { // 记录下元素所在的原始位置 return {flat.size(), row.size() - 1}; } flat.push_back(elem); } } // 如果没找到，返回{-1, -1} return {-1, -1}; } // 二分查找辅助函数 bool binarySearch(int* arr, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return true; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return false; } // 使用上述函数进行查找 int main() { std::vector<std::vector<int>> matrix = {{1, 3, 5}, {7, 9, 11}, {13, 15, 17}}; int value = 9; std::pair<int, int> result = flatten(matrix, value); if (result.first != -1) { std::cout << "找到了元素，它在原数组中的位置是(" << result.first << ", " << result.second << ")\n"; int row = result.first; int col = result.second; bool found = binarySearch(matrix[row].data(), 0, col, value); // 注意数据类型匹配 if (found) { std::cout << "并且在一维化后的数组中位于索引" << binarySearchResult << "\n"; } else { std::cout << "但在一维化后的数组中未找到\n"; } } else { std::cout << "元素不在数组中\n"; } return 0; } ``` 在这个例子中，`flatten` 函数将二维数组转换为一维，然后 `binarySearch` 用于在一个已排序的一维数组中查找目标值。注意，在二维数组的每个子数组中查找时，需要处理指针和索引的问题，例如 `matrix[row].data()` 用于获取子数组的首地址。