二维数组中的高效查找方法：从思路到实现

在处理二维数组相关问题时，如何高效地查找目标元素是一个常见的挑战。本文将围绕一个经典问题展开——在一个每行从左到右递增、每列从上到下递增的二维数组中，快速判断某整数是否存在，并提供具体的实现代码。

问题分析

我们面临的二维数组具有特殊的排序规则：

• 每行元素按照从左到右的顺序递增
• 每列元素按照从上到下的顺序递增

例如这样一个二维数组：

1  2  8  9
2  4  9  12
4  7  10 13
6  8  11 15

需要判断其中是否包含目标数字（如7），若存在返回true，否则返回false。

核心思路

常规的暴力遍历方法需要检查数组中的每一个元素，时间复杂度为O(rows×cols)，效率较低。而利用数组的排序特性，我们可以设计更高效的算法：

1. 选取右上角元素作为起始点：这个位置的元素是当前行的最大值，同时是当前列的最小值，具有特殊的比较意义
2. 逐步缩小范围：
3. 若当前元素等于目标值，查找成功
4. 若当前元素大于目标值，说明目标值不可能在当前列（因为列是递增的），剔除当前列
5. 若当前元素小于目标值，说明目标值不可能在当前行（因为行是递增的），剔除当前行
6. 重复操作：直到找到目标值或查找范围为空

这种方法每一步都能剔除一行或一列，时间复杂度优化为O(rows + cols)，大大提高了查找效率。

代码实现

C++实现

class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
    int rows = array.size();
    int cols = array[0].size();
    if(!array.empty() && rows > 0 && cols > 0){
        int row = 0;
        int col = cols - 1;
        while(row < rows && col >= 0){
            if(array[row][col] == target){
                return true;
            }
            else if(array[row][col] > target){
                --col;
            }
            else{
                ++row;
            }
        }
    }
    return false;
}
};

Python实现

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array)
        cols = len(array[0]) if rows > 0 else 0
        if rows > 0 and cols > 0:
            row = 0
            col = cols - 1
            while row < rows and col >= 0:
                if target == array[row][col]:
                    return True
                elif target < array[row][col]:
                    col -= 1
                else:
                    row += 1
        return False

总结

这个问题的解决关键在于充分利用数组的排序特性，通过巧妙选择起始点和设计缩小范围的规则，实现了高效查找。这种"逐步剔除"的思路在处理有序数据结构相关问题时具有广泛的应用价值，能够帮助我们在面对复杂问题时找到简洁高效的解决方案。