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

在C++中，二分查找通常用于一维有序数组，但对于二维数组，由于它是矩阵形式的数据结构，我们一般不会直接应用二分查找。因为二分查找依赖于元素的线性排列，而二维数组的索引通常是行优先（i, j）或列优先（j, i）。不过，如果你有一个预处理好的二维有序数组，并且想要查找特定值对应的位置，可以将其视为一维化后进行操作。

以下是一个简单的例子，假设我们要在一维化后的二维数组上进行二分查找：

#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()` 用于获取子数组的首地址。