1. 简述

    杨氏矩阵中，每行元素是递增的，每列元素也是递增的。即a[i][j]<a[i+1][j]且a[i][j]<a[i][j+1]。要在这样的矩阵中查找某个数值元素的位置，复杂度可以达到O(M+N)，其中M为矩阵行长度，N为矩阵列长度。

2. 原理

    从矩阵的左下角或者矩阵的右上角处开始递归运行，以左下角为例，value为要查找的值，(i,j)为当前矩阵中的位置，初始为(M-1, 0)。

    如果超过了矩阵范围则说明不存在这样的元素，返回-1，-1。

    否则的话，如果当前位置的值大于value，说明要移动位置，使得数值减小，即递归使得i=i-1；如果当前位置的值小于value，说明要移动位置，使得数值增大，即递归使得j=j+1；如果刚好等于value，返回当前的位置i，j即可。

3. 代码

#include 

<

iostream

>

using

 

namespace

 std;

#define

 M 5

#define

 N 4

int

 array[M][N] 

=

 {

1

,

2

,

3

,

4

,  

5

,

6

,

7

,

8

, 

9

,

10

,

11

,

12

, 

13

,

14

,

15

,

16

, 

17

,

18

,

19

,

20

};

void

 find_from_left_bottom(

int

*

a, 

int

 i,

int

 j, 

int

 m, 

int

 n, 

int

 value, 

int

&

 x, 

int

&

 y) {

  

if

(i

<

0

 

||

 j

>=

n)

    x 

=

 y 

=

 

-

1

;

  

else

 {

    

if

(

*

(a

+

i

*

n

+

j) 

<

 value) 

      find_from_left_bottom(a, i, j

+

1

, m, n, value, x, y);

    

else

 

if

(

*

(a

+

i

*

n

+

j) 

>

 value)

      find_from_left_bottom(a, i

-

1

, j, m, n, value, x, y);

    

else

 

      x 

=

 i, y 

=

 j;

  }

}

int

 main() {  

  

int

 x,y;

  

int

 value 

=

 

12

;

  find_from_left_bottom(array[

0

], M

-

1

, 

0

, M, N, value, x,y);

  cout 

<<

 x 

<<

 

"

  

"

 

<<

 y 

<<

 endl;

  cout 

<<

 array[x][y] 

<<

 endl;

  system(

"

PAUSE

"

);

  

return

 

0

;

} 

4. 备注

    最初遇到这道题的时候，纠结于把矩阵斜过来看，想用二分的方法，结果没成功。还是老魏同学找到这个方法给我说明的。

    另外，二维数组传递的时候，传int*就好了，反正通过函数传递后，数组的结构信息都会丢失，取得的就是普通的int *而不是行指针了，可以放心大胆的用*(a+i*n+j)，要注意其中的n是j下标对应的长度哦。

5. 参考

    杨氏矩阵算法和思维