遞歸查找有序二維數組：從右上角開始的高效策略

問題描述

給定一個 行遞增、列遞增 的二維陣列，判斷目標整數是否存在。例如 4×4 陣列：

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

查找數字 6。

核心演算法思想

關鍵觀察：右上角元素（或左下角）具有特殊性質——它是該行最大、該列最小。以右上角 (row=0, col=n-1) 為起點：

• 若目標 小於 當前元素 → 目標不可能在該列（因該列皆 ≥ 當前元素）→ 左移 (col--)
• 若目標 大於 當前元素 → 目標不可能在該行（因該行皆 ≤ 當前元素）→ 下移 (row++)
• 若 相等 → 找到，返回 true
• 若越界 → 不存在，返回 false

每步排除一行或一列，時間複雜度 O(m+n)，空間複雜度 O(1)（遞歸版為 O(m+n) 棧深度）。

遞歸實現

public class FindMatrixNumber {
    private static FindMatrixNumber instance;
    private static boolean found = false;

    public static FindMatrixNumber getInstance() {
        if (instance == null) {
            instance = new FindMatrixNumber();
        }
        return instance;
    }

    public static boolean find(int[][] matrix, int number) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        System.out.println("****Start finding****");
        findMatrixNumber(matrix, matrix.length, 0, matrix[0].length, number);
        System.out.println("*****End finding*****");
        return found;
    }

    private static void findMatrixNumber(int[][] matrix, int rows, int row, int columns, int number) {
        if (row > rows - 1) return; // 越界：行超出
        
        int cornerNumber = matrix[row][columns - 1]; // 右上角
        System.out.println(cornerNumber);
        
        if (cornerNumber == number) {
            found = true;
            return;
        } else if (cornerNumber < number) {
            findMatrixNumber(matrix, rows, ++row, columns, number); // 下移
        } else {
            findMatrixNumber(matrix, rows, row, --columns, number); // 左移
        }
    }
}

測試與輸出

public class TestFindMatrixNumber {
    public static void main(String[] args) {
        int[][] matrix = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
        System.out.println(FindMatrixNumber.find(matrix, 6));
    }
}

輸出追蹤：

****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true

路徑：9→8（左移）→2（下移）→4（下移）→7（左移）→4（下移）→6（找到）。

改進建議

• 避免使用 static boolean found 共享狀態，改為回傳值
• 單例模式此處非必要，靜態方法即可
• 可改為迭代寫法，避免棧溢出風險

迭代版參考

public static boolean findIterative(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0) return false;
    int row = 0, col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        int current = matrix[row][col];
        if (current == target) return true;
        else if (current < target) row++;
        else col--;
    }
    return false;
}