数据结构中的数组问题

来源：百度知道 编辑：UC知道 时间：2024/05/18 01:39:53
哪位高人帮帮忙！谢啦！题目是这样的
设定二维整数数组B[0..m-n,0..n-1]的数据结构在行、列方向上都按从小到大的顺序，且整型变量x中的数据在在B中存在。试设计一个算法，找出一对满足B[i][j]=x的i,j值。要求比较次数不超过m+n。

算法：

将X与数组B的第i其中(i=0，1，2，。。。m)行最后一个数比较，

1.如果X偏小，则将X与该行所有元素比较使得找出一对满足B[i][j]=x的i,j值，否则跳到第2步

2.将X与数组B的第i+1其中(i=0，1，2，。。。m)行最后一个数比较,如此循环

经过计算：最大次数m+n-1

想了一下，貌似做到m+n使有点困难。
提出一种思路：
1.如果b[i][j]>x 则对所有b[w][j],w>i或b[i][w],w>j,都大于x;
2.所以用2分找到b[0][w]恰好大于x,排除所有右边和下边的元素，队列向量也一样。
3.从对角线向上搜索，我认为只能线性了（无奈），直到找到x；

例：
0 2 3 4
1 5 6 7
8 9 10 11
12 13 14 15

要找9，二分找到列和行上的1