74. Search a 2D Matrix

Description:

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

Algorithm:

1. Squeeze from up and down
2. Squeeze from left and right

Code:

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0) return false;
int m = matrix.size();
int n = matrix[0].size();

int up = 0, down = m - 1;

int left = 0, right = n - 1;

while (up <= down)
{
int mid_ud = (up + down) / 2;
if (matrix[mid_ud][left] > target)
down = mid_ud - 1;
else if (matrix[mid_ud][right] < target)
up = mid_ud + 1;
else
{
while (left <= right)
{
int mid_lr = (left + right) / 2;
if (matrix[mid_ud][mid_lr] > target)
right = mid_lr - 1;
else if (matrix[mid_ud][mid_lr] < target)
left = mid_lr + 1;
else
return true;
}
return false;
}
}
return false;
}
};

Timing:

Fastest, 6ms

O(logm+logn) // m is the row and n is the column