本文共 2056 字，大约阅读时间需要 6 分钟。

在二维数组中查找特定数字的两种方法

方法一：顺序查找 + 折半查找

思路

在二维数组中查找特定数字，首先需要确定目标数字可能存在的行。根据二维数组的性质，每行都是有序的，因此我们可以通过顺序查找确定目标值可能所在的行。具体来说，只有某一行的最小值小于等于目标值，而最大值大于等于目标值时，目标值才有可能位于该行。找到该行后，可以对该行进行折半查找来快速定位目标值。

代码

class Solution:
    public:
        bool findNumberIn2DArray(vector
   
    
     > &matrix, int target) {
            if (matrix.empty() || matrix[0].empty()) {
                return false;
            }
            for (int i = 0; i < matrix.size(); ++i) {
                if (matrix[i][0] <= target && matrix[i][matrix[0].size() - 1] >= target) {
                    if (binarySearch(matrix[i], target)) {
                        return true;
                    }
                }
            }
            return false;
        }
        bool binarySearch(vector
     
       a, int target) {
            int left, right;
            left = 0;
            right = a.size() - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (a[mid] == target) {
                    return true;
                } else if (a[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return false;
        }
     
    
   

方法二：基于二叉搜索树的方法

思路

由于二维数组的每一行从左到右是递增的，每一列从上到下也是递增的，因此整个数组可以看作是一个二叉搜索树。右上角是一个特殊的位置，因为它左边的所有元素都小于它，下边的所有元素都大于它。基于这一特性，我们可以从右上角开始搜索，向左或向下移动，直到找到目标值或确定目标值不存在。

代码

class Solution:
    public:
        bool findNumberIn2DArray(vector
   
    
     > &matrix, int target) {
            if (matrix.empty() || matrix[0].empty()) {
                return false;
            }
            int row = 0, column = matrix[0].size() - 1;
            while (row < matrix.size() && column >= 0) {
                if (matrix[row][column] == target) {
                    return true;
                } else if (matrix[row][column] > target) {
                    --column;
                } else {
                    ++row;
                }
            }
            return false;
        }
    
   

以上两种方法都能高效地在二维数组中查找特定数字，适用于不同的场景。