2D Peak Finding算法失效问题咨询（附C++实现代码）

我仔细看了你的代码和测试输入，发现核心问题出在递归过程中搜索范围的管理逻辑错误，还有几个潜在的边界处理问题，下面一步步拆解：

1. 递归逻辑的核心错误：未维护搜索区间 #

你的findPeakRec函数仅通过mid计算新的中间列，没有维护当前搜索的列范围（左、右边界），这会导致两种严重问题：

• 无限递归风险：比如当某两列的最大值互相"引诱"时（例如列1的最大值右侧更大，列2的最大值左侧更大），代码会在两个mid值之间来回跳转，陷入无限递归，最终栈溢出。
• 边界判断错误：原代码中当mid == 0或mid == columns-1时直接返回最大值，但此时该列的最大值可能被相邻列的元素更大（比如mid=0时，右侧列对应位置元素更大），直接返回会得到错误结果。

2. 其他潜在问题 #

• 最大值初始化错误：findMax函数中max初始值设为0，若数组中存在负数元素，会导致无法正确找到列的最大值。
• 变量命名冲突：使用max作为变量名，而max是C++标准库的函数名，属于不良编程习惯。
• 数组越界风险：当mid为0时，代码仍可能尝试访问mid-1的位置，引发未定义行为。

正确的实现思路与修改后的代码 #

正确的2D Peak Finding算法需要维护当前搜索的列区间[left, right]，每次通过二分缩小范围，直到找到峰值：

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;

// 找到指定列的最大值所在行，并返回最大值
int findMaxRow(int arr[][MAX], int rows, int col, int& max_val) {
    int max_row = 0;
    max_val = arr[0][col]; // 初始化为列首元素，避免负数问题
    for (int i = 1; i < rows; ++i) {
        if (arr[i][col] > max_val) {
            max_val = arr[i][col];
            max_row = i;
        }
    }
    return max_row;
}

int findPeakRec(int arr[][MAX], int rows, int left, int right) {
    int mid = left + (right - left) / 2; // 避免整数溢出
    int max_val;
    int max_row = findMaxRow(arr, rows, mid, max_val);
    
    // 检查左侧是否有更大元素，缩小到左半区间
    if (mid > left && arr[max_row][mid-1] > max_val) {
        return findPeakRec(arr, rows, left, mid - 1);
    }
    // 检查右侧是否有更大元素，缩小到右半区间
    if (mid < right && arr[max_row][mid+1] > max_val) {
        return findPeakRec(arr, rows, mid + 1, right);
    }
    // 满足峰值条件：当前元素是列最大值，且左右无更大元素（或已到边界）
    return max_val;
}

int findPeak(int arr[][MAX], int rows, int columns) {
    return findPeakRec(arr, rows, 0, columns - 1);
}

int main() {
    int arr[][MAX] = { { 5, 0, 3, 2 }, { 1, 1, 2, 4 }, { 1, 2, 4, 4 }, { 3, 2, 0, 1 } };
    int rows = 4, columns = 4;
    cout << findPeak(arr, rows, columns) << endl; // 输出4，正确
    return 0;
}

修改关键点说明 #

1. 维护搜索区间：递归函数接收left和right作为当前搜索的列范围，每次明确缩小到左半或右半区间，彻底避免无限递归和范围错误。
2. 正确初始化最大值：将最大值初始化为列的第一个元素，兼容负数数组的情况。
3. 安全的边界检查：判断左右列是否存在后再访问元素，避免数组越界。
4. 避免溢出：使用mid = left + (right - left)/2代替(left+right)/2，防止大整数相加溢出。

对于你的测试输入，修改后的代码会正确返回4——这是一个有效的2D峰值（它大于上下元素，且右侧元素等于它，符合算法中"大于等于"的峰值定义）。

内容的提问来源于stack exchange，提问作者Atom