博文中会简要介绍Leetcode P0074题目分析及解题思路。
“Search a 2D Matrix”是一道比较有意思的题目，考察的重点在于灵活运用二分查找算法。
Write an efficient algorithm that searches for a value in an m x n 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. Example 1:
Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true
分成两部分来二分查找，对第一列二分查找，然后对指定行二分查找。
以下是Java的题解代码实现。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0)
return false;
int up = 0, down = matrix.length-1, midRow = 0;
while (up <= down) {
midRow = (up+down)/2;
if (matrix[midRow][0] > target)
down = midRow-1;
else if (matrix[midRow][0] < target)
up = midRow+1;
else
return true;
}
if (matrix[midRow][0] > target)
midRow -= 1;
if (midRow < 0)
return false;
int left = 0, right = matrix[0].length-1, midCol = 0;
while (left <= right) {
midCol = (left+right)/2;
if (matrix[midRow][midCol] > target)
right = midCol-1;
else if (matrix[midRow][midCol] < target)
left = midCol+1;
else
return true;
}
return false;
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0)
return false;
int up = 0, down = matrix.size()-1, midRow = 0;
while (up <= down) {
midRow = (up+down)/2;
if (matrix[midRow][0] > target)
down = midRow-1;
else if (matrix[midRow][0] < target)
up = midRow+1;
else
return true;
}
if (matrix[midRow][0] > target)
midRow -= 1;
if (midRow < 0)
return false;
int left = 0, right = matrix[0].size()-1, midCol = 0;
while (left <= right) {
midCol = (left+right)/2;
if (matrix[midRow][midCol] > target)
right = midCol-1;
else if (matrix[midRow][midCol] < target)
left = midCol+1;
else
return true;
}
return false;
}
};