返回信息流已知一个m*n矩阵(用数组存储),且其由上到下,由左到右均按由小到大排列,请教算法,
使得只用<=m+n次便可找出其中的一个数x的位置.(为方便,假定m>=n).
这是一条镜像帖。来源：北邮人论坛 / soft-design / #7007同步于 2006/5/2
该镜像源已超过 30 天没有更新，可能在源站已被删除。
SoftDesign机器人发帖
[求助]矩阵算法
Cloudeagle
2006/5/2镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
[code]
#include <stdio.h>
#define M 3
#define N 3
int num[M][N] =
{
{10, 20, 30},
{11, 21, 31},
{12, 22, 32}
};
int main()
{
printf("m + n = %d\n", M + N);
int count = 0;
int x = 0, y = M - 1;
int aim = 21;
while (x < N && y > -1) {
count++;
if (num[y][x] == aim) {
printf("num[%d][%d] = %d, count = %d\n", y, x, aim, count);
return 0;
} else if (num[y][x] > aim) {
y--;
} else {
x++;
}
}
printf("not found. count = %d\n", count);
}
[/code]
原则是
在当前比较点如果目标大于当前数就横向向大数方向搜索,
如果目标小于当前数就纵向向小数方向搜索
由于前进方向均不可逆(向右或者向上), 那么最大搜索距离就是M+N