大多数人注意到元素是行列有序的，会马上想到对每行（或列）进行二分查找，每行(或列)需要logN时间，N行（或列）共需要NlogN时间，很容易写出如下代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//注意到元素是行列有序的，会马上想到对每行（或列）进行二分查找，每行(或列)需要logN时间，N行（或列）共需要NlogN时间bool Find (vector< vector<int > > array, int target ) {
int rowNum =array. size();
int colNum =array[0]. size();
int row ,col;
for (row = 0; row < rowNum; row ++)
{
int l = 0, r = colNum - 1;
while (l <= r)
{
col = (l + r) >> 1;
if (array [row][ col] == target ) return true;
else
if (array [row][ col] < target )
l = col + 1;
else r = col - 1;
}
}
return false ;
} |
对角二分搜索相似，我们从右上角开始（从左下角开始也一样）。此时我们不是每步走一个对角，而是
每步往左或者往下走。我们称这种方法为步进线性搜索（Step‐wise Linear Search），下图6描述了查找元素13的路径。
这样每步都能扔掉一行或者一列。最坏情况是被查找元素位于另一个对角，需要2N步。因此这个算法是O（N）的，比先前的方法都好，而且代码简洁直接。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
//步进线性搜索（Step‐wise Linear Search）
int rowNum=array.size();
int colNum=array[0].size();
int row,col;
row = 0;
col = colNum - 1; //从array[0][colNUM]开始搜索，即右上角
while (row < rowNum && col >= 0)
{
if (array[row][col] == target) return true;
else
if (array[row][col] < target) //如果当前指向元素小于目标，则下移
row++;
else if(array[row][col] >target) //否则，左移
col--;
}
return false;
}
}; |