题意整理

• 给定一个有序矩阵mat和待查找元素x，矩阵的行和列都是从小到大有序的。
• 求x在矩阵中的位置，以二元数组的形式返回。

方法一（二分）

1.解题思路

• 遍历所有行，对每一行所有元素进行二分查找。
• 如果找到，直接返回。如果小于x，则排除左边所有元素。如果大于x，则排除右边所有元素。

2.代码实现

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        //遍历所有行
        for(int i=0;i<n;i++){
            //对当前行所有元素进行二分查找
            int l=0,r=m-1;
            while(l<=r){
                int mid=l+(r-l)/2;
                //如果找到，直接返回
                if(mat[i][mid]==x){
                    return new int[]{i,mid};
                }
                else if(mat[i][mid]<x){
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
        }
        return new int[0];
    }
}

3.复杂度分析

• 时间复杂度：需要遍历所有行，每一行查找次数为$lo{g}_{2}mlog\_2m$，所以时间复杂度为$O(nlo{g}_{2}m)O(nlog\_2m)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。

方法二（二分优化）

1.解题思路

方法一只利用了每一行有序的条件，没有用到列也是有序的。根据行列都有序的特点，可以把矩阵逆时针旋转45度，矩阵就会变成类似二叉搜索树的结构，左边总是小于当前节点，而右边总是大于当前节点，利用这个特点进行二分搜索。

• 总右上角出发，开始进行查找。
• 如果找到，直接返回。如果小于x，则往下一行继续查找。如果大于x，则往前一列继续查找。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        //初始查找位置的行和列（右上角）
        int row=0;
        int col=m-1;
        //只要没有超出边界
        while(row<=n-1&&col>=0){
            //如果找到，直接返回
            if(mat[row][col]==x){
                return new int[]{row,col};
            }
            //如果小于x，则往下一行继续查找
            else if(mat[row][col]<x){
                row++;
            }
            //如果大于x，则往前一列继续查找
            else{
                col--;
            }
        }
        return new int[0];
    }
}

3.复杂度分析

• 时间复杂度：从开始到结束，最多移动n行和m列，所以时间复杂度为$O(n+m)O(n+m)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。