参考答案

正确答案：void search(datatype A[ ][ ]int abCddatatype X)／／nxm矩阵A行下标从a到b列下标从C到d本算法查找X是否在矩阵A中{i=a；j=d；flag=0；／／flag是成功查到X的标志while(i<=b&&j>=C)if(A[i][J]==x){flag=1；break；}else if(A[i][J]>x)j一一；else i++；if(flag)printf(“A[％d][％d]=％d”ijx)；／／假定x为整型else printf(”矩阵A中无％d元素”x)；}／／算法search结束
此问题考查的知识点是矩阵的查找。由于矩阵中元素按行和按列都已排序，要求查找时间复杂度为0(m+n)，因此不能采用常规的二层循环的查找。可以先从右上角(i=a，j=d)元素与x比较，只有三种情况：一是A[i，j]>x，这情况下向j小的方向继续查找；二是A[i，j]<x，下一步应向i大的方向查找；三是A[i，j]=x，查找成功。否则，若下标已超出范围，则查找失败。算法中查找x的路线从右上角开始，向下(当x>A[i，j])或向左(当x<A[i，j])。向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角(A[6，c])，比较m+n次，故算法最差时间复杂度是D(m+n)。