有序二維矩陣中的目標值查找

1. 題目描述

給定一個元素為非負整數的二維數組matrix，其中：

• 每一行按照從左到右遞增的順序排列
• 每一列按照從上到下遞增的順序排列

再給定一個非負整數aim，請判斷aim是否存在于matrix中。

示例：

int[][] matrix = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}
};
int aim = 5; // 返回true
int aim = 15; // 返回false

2. 問題解釋

• 矩陣行列均有序，但不像完全排序的一維數組那樣可以直接二分
• 需要利用行列有序的特性設計高效查找算法
• 暴力搜索時間復雜度為O(m*n)，不夠高效
• 目標是設計優于O(m*n)的算法

3. 解決思路

方法一：逐行二分查找（適合行數較少的情況）

• 對每一行進行二分查找
• 時間復雜度：O(m log n)，m為行數，n為列數

方法二：利用行列有序特性（最優解）

1. 從矩陣的右上角開始查找（或左下角）
2. 比較當前元素與目標值：
   • 如果等于目標值，返回true
   • 如果大于目標值，排除當前列（向左移動）
   • 如果小于目標值，排除當前行（向下移動）
3. 時間復雜度：O(m + n)

4. 代碼實現

public class SearchInSortedMatrix {// 方法一：逐行二分查找public boolean searchMatrixByRowBinarySearch(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}for (int[] row : matrix) {if (binarySearch(row, target)) {return true;}}return false;}private boolean binarySearch(int[] row, int target) {int left = 0, right = row.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (row[mid] == target) {return true;} else if (row[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return false;}// 方法二：利用行列有序特性（最優解）public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}int row = 0;int col = matrix[0].length - 1; // 從右上角開始while (row < matrix.length && col >= 0) {if (matrix[row][col] == target) {return true;} else if (matrix[row][col] > target) {col--; // 排除當前列} else {row++; // 排除當前行}}return false;}public static void main(String[] args) {SearchInSortedMatrix solution = new SearchInSortedMatrix();int[][] matrix = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}};System.out.println(solution.searchMatrix(matrix, 5)); // trueSystem.out.println(solution.searchMatrix(matrix, 15)); // falseSystem.out.println(solution.searchMatrixByRowBinarySearch(matrix, 9)); // trueSystem.out.println(solution.searchMatrixByRowBinarySearch(matrix, 20)); // false}
}

5. 總結

1. 方法選擇：

   • 當行數遠小于列數時，方法一（逐行二分）可能更優
   • 一般情況下，方法二（行列排除法）是最優解

2. 復雜度分析：

   • 方法一：O(m log n)
   • 方法二：O(m + n)

3. 關鍵點：

   • 利用矩陣行列有序的特性
   • 選擇合適的起點（右上角或左下角）
   • 每次比較都能排除一行或一列

4. 擴展思考：

   • 如果矩陣是完全排序的（即展平后有序），可以直接使用一維二分查找
   • 如果矩陣中存在重復元素，算法依然適用

5. 實際應用：

   • 數據庫索引查找
   • 圖像處理中的像素查找
   • 游戲地圖中的坐標查找