搜索二维矩阵---二分查找

搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：二分

先查找target在哪一行，二分查找第一列即可。再在对应的行上进行二分查找。

code

class Solution {
public:
    
    //首先判断target在哪一行，也就是二分查找第一列，划分为target<=以及>target,查找小于等于target的右端点
    //再在对应的行上二分查找
    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int l = 0,r = matrix.size() -1;
        
        while(l < r)
        {
            int mid = (l + r + 1) /2;

            if(matrix[mid][0] <= target) l = mid;
            else r = mid -1;
        }
        
        //cout<<l<<endl;
        int i = 0,j = matrix[0].size();

        while(i < j)
        {
            int mid = (i + j) /2;
            if(matrix[l][mid] >= target) j = mid;
            else i = mid + 1;
        }
        
        if(l < matrix.size() && i < matrix[0].size() && matrix[l][i] == target) return true;
        else return false;

    }
};

解题思路2：一次二分查找

将一维数组映射为二维即可，就像之前写的cuda矩阵乘法一样，不是将二维数组拷贝到GPU上，而是在GPU上用一维数组模拟二维数组。这样就不用额外开空间了。