LeetCode Search a 2D Matrix：二維有序矩陣查找兩種 O(log mn) 解法

解法二：從右上角（或左下角）搜索

起點 (0, n-1)：若當前 > target 向左，< target 向下，相等返回 true。每步排除一行或一列。

int i=0, j=n-1;
while (i=0) {
    if (matrix[i][j]==target) return true;
    else if (matrix[i][j] > target) --j;
    else ++i;
}
return false;

比較

• 二分法：O(log mn)，代碼簡潔，需矩陣完全有序（題目滿足）。
• 右上角法：O(m+n)，但更通用（僅需行列各自有序，無需行首 > 前行尾）。

完整 Java 代碼（二分法）

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix==null || matrix.length==0) return false;
        int m=matrix.length, n=matrix[0].length;
        int lo=0, hi=m*n-1;
        while (lo<=hi) {
            int mid = lo + (hi-lo)/2;
            int val = matrix[mid/n][mid%n];
            if (val==target) return true;
            else if (val