Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3,
return true.
什么叫丧心病狂？m+n已经不能满足人类的欲望了，如果用二路二分，效率可达O(log m + log n)
我就不丧心病狂了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 |
class
Solution {public: bool
searchMatrix(vector<vector<int> > &matrix, int
target) { int
x = matrix.size(); int
y = matrix[0].size(); if(x==0)return
false; int
i; for(i = 0 ; i < x-1 ;i++) if(matrix[i+1][0] > target)break; else
if(matrix[i+1][0] == target)return
1; if(matrix[x-1][0] < target) i = x-1; if(matrix[x-1][0] == target) return
1; int
j = 0; for( j = 0 ; j < y-1 ;j++) if(matrix[i][j] == target)return
1; else
if(matrix[i][j+1] > target)break; if(matrix[i][j] == target)return
1; return
0; }}; |
Search a 2D Matrix,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3599217.html