Leetcode 240. 搜索二维矩阵 II 暴力与二分

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

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
 

提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

解答
第一印象是暴力遍历，然后做了一些剪枝，避免重复无效的比较查找
能AC 但是效率较低

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size();i++){
            if(matrix[i][0] > target){break;}
            if( matrix[i].back() < target) {continue;}
            for(int j = 0; j < matrix[0].size();j++){
                if(matrix[i][j]> target) {break;}
                if(matrix[i][j] == target) return true;    
            }
        }
        return false;
    }
};

优化方案。 由于矩阵是有序排列，每行的查找可以使用二分。

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

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size();i++){
            if(matrix[i][0] > target){break;}
            if( matrix[i].back() < target) {continue;}
            if(bsearch(matrix,target,i) == true) return true;
        }
        return false;
    }
};

我的视频题解空间

Leetcode 240. 搜索二维矩阵 II 暴力与二分

原文：https://www.cnblogs.com/itdef/p/15260085.html