# LeetCode 74:Search a 2D Matrix

Datetime:2016-08-23 01:21:46         Topic: LeetCode          Share        Original >>

Write an efficient algorithm that searches for a value in an mn matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

```[
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]```

Given target`3` , return  `true` .

Subscribe to see which companies asked this question

```class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0)     return false;
if (matrix[0][0] > target)  return false;
int r = matrix.size(), c = matrix[0].size(); //r,c分别为矩阵matrix的行数和列数
int low = 0, high = r-1;

//在所有行中利用二分查找target所在的行
while(low <= high)
{
int mid = low + (high-low) / 2;
if (matrix[mid][0] == target)
return true;
else if (matrix[mid][0] < target)
low = mid + 1;
else
high = mid - 1;
}

//在target所在行中利用二分查找target
int low1 = 0, high1 = c - 1;
int k = 0;
while (low1 <= high1)
{
int mid1 = low1 + (high1 - low1)/2;
if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
return true;
else if (matrix[low-1][mid1] < target)
low1 = mid1 + 1;
else
high1 = mid1 - 1;

k = mid1;
}

if (matrix[low-1][k] == target)
return true;
else
return false;
}
};```

```#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0)     return false;
if (matrix[0][0] > target)  return false;
int r = matrix.size(), c = matrix[0].size(); //r,c分别为矩阵matrix的行数和列数
int low = 0, high = r-1;

//在所有行中利用二分查找target所在的行
while(low <= high)
{
int mid = low + (high-low) / 2;
if (matrix[mid][0] == target)
return true;
else if (matrix[mid][0] < target)
low = mid + 1;
else
high = mid - 1;
}

//在target所在行中利用二分查找target
int low1 = 0, high1 = c - 1;
int k = 0;
while (low1 <= high1)
{
int mid1 = low1 + (high1 - low1)/2;
if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
return true;
else if (matrix[low-1][mid1] < target)
low1 = mid1 + 1;
else
high1 = mid1 - 1;

k = mid1;
}

if (matrix[low-1][k] == target)
return true;
else
return false;
}
};

int main()
{
Solution s;
vector<vector<int>> nums1 = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, {23,30,34,50} };
bool  t = s.searchMatrix(nums1, 11);
cout << t <<endl;
system("pause");
return 0;
}```