题目
原文：
Given a matrix in which each row and each column is sorted, write a method to find an element in it.
译文：
给出一个矩阵，其中每一行和每一列都是有序的，写一个函数在矩阵中找出指定的数。
解答
我们假设这个矩阵每一行都是递增的，每一列也都是递增的，并把这些数据存入文件 9.6.in(如下)，其中开头的两个数5 5表示该矩阵是5*5的。
1
2
3
4
5
6
5 5
1 2 3 4 5
3 7 8 9 11
5 9 10 17 18
7 12 15 19 23
9 13 16 20 25
这个矩阵是有序的，因此我们要利用这一点，当矩阵中元素和要查找的元素对比后， 如果相等，我们返回下标；如果不等，我们就排除掉一些元素，而不仅仅是对比的元素。 我们从矩阵的四个角的元素入手看看，有什么特点。左上角是最小的， 因为矩阵向右是递增的，向下也是递增的。同理，右下角是最大的。让我们来看看右上角， 设要查找的元素为x，比如x比右上角元素5大，那么它也会比第一行的其它元素都大。 因此可以去掉第一行；如果它比右上角元素小，那么它也会比最后一列的元素都小， 因此可以去掉最后一列；然后这样不断地比下去，只需要O(m+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
28
#include <iostream>
#include <cstdio>
using namespace std;
int d[20][20];
int search(int m, int n, int x){
int r = 0, c = n-1;
while(r<m && c>=0){
if(d[r][c] == x) return (r * n + c);
else if(d[r][c] < x) ++r;
else --c;
}
return -1;
}
int main(){
freopen("9.6.in", "r", stdin);
int m, n;
cin>>m>>n;
for(int i=0; i<m; ++i)
for(int j=0; j<n; ++j)
cin>>d[i][j];
int k = search(m, n, 13);
if(k == -1) cout<<"not found"<<endl;
else cout<<"position: "<<k/n<<" "<<k%n<<endl;
fclose(stdin);
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/01/21/9.6/
