求一个优于O(n^2)的算法
一个N*N的矩阵，从左至右，右边的数比左边的数，下边的数比上面的数大，现在给定某一个数N，求搜索到它的一个优于O(n^2）的算法~

[解决办法]
lz搜索杨氏矩阵查找。
[解决办法]

C/C++ code

#include<iostream>#include<string>using namespace std;const int MM=1005;int map[MM][MM],N,M; int search(int x,int y,int key,int &px,int &py){//从矩阵的左下角开始查找     if(x<0 || y>=M)         return 0;     if(map[x][y]<key)          return search(x,y+1,key,px,py);    else if(map[x][y]>key)         return search(x-1,y,key,px,py);    else{          px=x, py=y;         return 1;     } } int main(){    while(scanf("%d%d",&N,&M)==2){         for(int i=0;i<N;++i) //输入矩阵，N行，M列，下标从0开始              for(int j=0;j<M;++j)                 scanf("%d",&map[i][j]);         int key;          while(cin>>key){  // 查找key              int px,py;              if(search(N-1,0,key,px,py)){ //返回的（px,py)是key在矩阵中的最后一个位置                  puts("have find");                  printf("px == %d , py == %d \n",px,py);              }              else                 puts("not find");          }    }    return 0;}
[解决办法]
从右上角往下走，遇到超过的数值，改变方向
只有两个方向：往下，或往左
只有两个结果：找到了或走出去了

Python code
def foo(M,n):    l = len(m)     x,y = l-1,0    goDown = True    while M[y][x]!=n:        if M[y][x] > n and goDown:            goDown = False        elif M[y][x]<n and not goDown:            goDown = True        if goDown:            y+=1        else:            x-=1        if x<0 or y>=l:            return ('not found!')    return x,ym = ((0,2,4,6,8),     (3,5,7,9,10,),     (4,8,10,11,16,),     (6,9,13,15,18),     (8,10,17,19,21)     )print(foo(m,15))print(foo(m,11))print(foo(m,7))print(foo(m,17))print(foo(m,20))print(foo(m,1))print(foo(m,12))