搜索二维矩阵

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

样例输入

示例 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

 

题解

解1

• 对于每一行，先判断target是否在该行中
• 如果在改行中，则使用二分进行寻找

class Solution {
bool searchTarget(vector<int>& nums,int& target)
{
    int left=0,right=nums.size()-1;
    while(left<=right)
    {
        int mid=left+((right-left)>>1);
        if(target==nums[mid]) return true;
        if(target<nums[mid]) right=mid-1;
        if(target>nums[mid]) left=mid+1;
    }
    return false;
}
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(vector<int>&nums: matrix)
        {
            if(target==nums[0] || target==nums[nums.size()-1]) return true;
            if(nums[0]<target && target<nums[nums.size()-1])
                return searchTarget(nums,target);
        }
        return false;
    }
};

解2

• 直接将二维数组看做一个一维数组，找到中间值：l=0;r=m*n-1;mid=(l+r)/2
• 计算这个“一维数组”中的中间值在二维数组中的位置
  • 其中行=mid/n
  • 列=mid%n

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        if(!m) return false;
        int n=matrix[0].size();
 
        int left=0,right=m*n-1;
        while(left<=right)
        {
            int mid=left+((right-left)>>1);
            int privlot=matrix[mid/n][mid%n];
            if(privlot==target) return true;
            if(target<privlot) right=mid-1;
            if(target>privlot) left=mid+1;
        }
        return false;
    }
};