解法1:右上左下进行遍历
根据题意从右上或者左下进行遍历找值
time: O(m + n)
public class Solution {
public boolean Find(int target, int [][] array) {
if (array == null || array.length == 0 || array[0] == null || array[0].length == 0) {
return false;
}
int row = 0;
int col = array[0].length - 1;
while (row <= array.length - 1 && col >= 0) {
if (target == array[row][col]) {
return true;
} else if (target < array[row][col]) {
col--;
} else {
row++;
}
}
return false;
}
}
解法2: 二分搜索法
逐层遍历,每层中采用二分搜索策略
time: O(mlogn)
public class Solution {
public boolean Find(int target, int [][] array) {
if (array == null || array.length == 0 || array[0] == null || array[0].length == 0) {
return false;
}
for (int i = 0; i < array.length; i++) {
int low = 0;
int high = array[i].length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (array[i][mid] == target) {
return true;
} else if (array[i][mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return false;
}
}