NO.74 搜索二维矩阵 中等
思路一：暴力 遍历数组。
思路二：二分法 数组的特性是有序的，很明显需要去二分。
如果我们创建一个大小是r*c的一维数组，将二维数组的值拷贝一份，那么就变成了熟悉的二分查找了。
但是实际上比不需要创建这么一个一维数组，因为二维数组每个元素本身的索引就是有序的。
直接将二维数组看作是索引区间是[0,r*c-1]的一维数组即可，这样我们可以很熟悉的找到start、end、mid，需要思考的就是将mid索引转换成二维数组中对应的元素下标。
[0,r*c-1]中的任何一个索引idx都可以通过matrix[idx/c][idx%c]的形式转换成二维数组中的准确元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;
int r = matrix.length, c = matrix[0].length;
int start = 0, end = r * c - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (matrix[mid / c][mid % c] == target) {
return true;
} else if (matrix[mid / c][mid % c] < target) {
start = mid + 1;
} else if (matrix[mid / c][mid % c] > target) {
end = mid - 1;
}
}
return false;
}
|
时间复杂度：O(log(r*c))
本人菜鸟，有错误请告知，感激不尽！
更多题解和源码:github