面试题 4：二维数组中的查找.md

试题链接：15. 二维数组中的查找 - AcWing题库

方法一：排除法

• 思路：从右上角的元素开始，若当前元素大于目标元素，则排除这一列，若小于目标元素则排除这一行。
• 时间复杂度：O(n + m)
• 空间复杂度：O(1)

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        int n = array.size();
        if (n == 0) return false;
        int m = array[0].size();
        if (m == 0) return false;
        
        int i = 0, j = m - 1;
        
        while (i < n && j >= 0) {
            if (array[i][j] == target) return true;
            if (array[i][j] > target) j--;
            else i++;
        }
        
        return false;
    }
};

方法二：二分法优化排除法

• 思路：排除方法从单行排除优化为多行排除。
• 时间复杂度：O(logn + logm)
• 空间复杂度：O(1)

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        int n = array.size();
        if (n == 0) return false;
        int m = array[0].size();
        if (m == 0) return false;
        
        int i = 0, j = m - 1;
        
        while (i < n && j >= 0) {
            if (array[i][j] == target) return true;
            if (array[i][j] > target) {
                if (j == 0) return false;
                int l = 0, r = j - 1;
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    if (array[i][mid] <= target) l = mid;
                    else r = mid - 1;
                }
                j = l;
            } else {
                if (i == n - 1) return false;
                int l = i + 1, r = n - 1;
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    if (array[mid][j] <= target) l = mid;
                    else r = mid - 1;
                }
                i = l;
            }
        }
        
        return false;
    }
};