LeetCode 240 Search a 2D Matrix II

    
        标签：
        
            二分搜索
        
            LeetCode
        
    发布于：2022-03-06 11:06:03
    编辑于：2022-03-06 11:15:37
    浏览量：891

概述

https://leetcode.com/problems/search-a-2d-matrix-ii/

二分搜索

我原本想的是，首先用二分搜索找到所在列，再用二分搜索搜索该列。

这种想法是错误的，

我们应当进行二维的二分搜索。

实现的时候注意：

首先，行是一级索引，列是二级索引，别搞错了；
其次，当遇到左边界和上边界无法继续更新时，我们需要搜索两条线（外加一个点），而非单纯的一个 2x2 方格

可以了，这种想法依然是错的。我们每次缩小范围时，其实根本不能确定目标值是否在那个方框内。

7 连 WA 和 RE，够了，就这样吧

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int l = 0, r = matrix[0].size() - 1;
        int t = 0, b = matrix.size() - 1;
        while (l <= r && t <= b) {
            int m1 = (t + b) / 2;
            int m2 = (l + r) / 2;
            // cout << m1 << " " << m2 << endl;
            if (m1 == t && m2 == l) {
                // cout << "bingo " << m1 << " " << m2 << endl;
                for (int row = m1, col = m2; col < matrix[0].size(); col ++) {
                    if (matrix[row][col] == target) return true;
                    if (matrix[row][col] > target) break;
                }
                for (int row = m1, col = m2; row < matrix.size(); row ++) {
                    if (matrix[row][col] == target) return true;
                    if (matrix[row][col] > target) break;
                }
                if (m1 + 1 < matrix.size() && m2 + 1 < matrix[0].size()) {
                    if (matrix[m1+1][m2+1] == target) return true;
                }
                return false;
            }
            
            if (matrix[m1][m2] == target) {
                return true;
            } else if (matrix[m1][m2] > target) {
                r = m2;
                b = m1;
            } else {
                l = m2;
                t = m1;
            }
        }
        return false;
    }
};

从右上角开始搜索

https://leetcode.com/problems/search-a-2d-matrix-ii/discuss/66139/C%2B%2B-search-from-top-right

因为从右上角搜索，每次：

我们要么找到目标值，
要么可以排除该列，
要么可以排除该行，

时间复杂度 O(m+n)。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int r = 0, c = matrix[0].size() - 1;
        while (r < matrix.size() && c >= 0) {
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] > target) {
                c --;
            } else {
                r ++;
            }
        }
        return false;
    }
};

Links: leetcode-240-search-a-2d-matrix-ii