正文
[算法][LeetCode]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.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
分析
一开始写的时候把他拆分成了两个二分查找，先纵向找，再横向找。纵向的二分查找比较复杂，要确定是在某个坐标上，或者在两个坐标之间。
后来找到一个更好的方法，就是把二维数组的坐标转化成一位数组，整体进行二分查找，程序更简单，复杂度也更低了。
Java代码public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) {
return false;
} int xLength = matrix[0].length;
int min = 0;
int max = matrix[0].length * matrix.length - 1; int x, y, current;
while (min <= max) {
current = (min + max) / 2;
y = current / xLength;
x = current % xLength;
if (matrix[y][x] == target) {
return true;
} else if (target < matrix[y][x]) {
max = current - 1;
} else {
min = current + 1;
}
} return false;
}
public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) {
return false;
} int xLength = matrix[0].length;
int min = 0;
int max = matrix[0].length * matrix.length - 1; int x, y, current;
while (min <= max) {
current = (min + max) / 2;
y = current / xLength;
x = current % xLength;
if (matrix[y][x] == target) {
return true;
} else if (target < matrix[y][x]) {
max = current - 1;
} else {
min = current + 1;
}
} return false;
}
