【C++】12行代码 从左下角开始二分搜索

将每一个元素视作L左下角的数字，由矩阵性质可知L也是从小到大有序的，所以左下角数比上边所有数大，比右边所有数小。当左下角数大于x时，比左下角数更大的右边的数可以全部舍弃，于是左下角上移一格；当左下角数小于x数，比左下角数小的上边的数可以全部舍弃，于是左下角右移。最多可以舍弃n行m列（找到值的时候不舍弃直接返回了），所以时间复杂度最坏是O（n+m）

class Solution {
public:
    vector<int> findElement(vector<vector<int> > &mat, int n, int m, int x) {
        int a = n - 1, b = 0; //左下角坐标
        while(a >= 0 && b < m) { //防止越界
            if(mat[a][b] == x) return vector<int> {a, b};
            else if(mat[a][b] < x) b++; //左下角右移
            else a--; //左下角上移
        }
        return vector<int> {0, 0};
    }
};