关于查找的算法问题

Question

题目如下：
已知数组B[m+1][n+1],每一维上的数均是由小到大存储的.写出算法,在数组中查找给
定的数x(已知x在B中是存在的)的算法(结果要求得到其坐标的i和j的值),要求比较次数
不超过(m+n)
请各位指教，谢谢！

Answer 1

在一维有序数组中查找，用折半法，比较次数肯定小于数据总数的。
那么对于二维有序数组来说，第一次查找只要找到B[m+1][0]中的m就可以了，次数肯定小于n，第二次查找肯定小于m，想不行都难。

Answer 2

Re  common_man(谢安王导) 
Mackz(在相互)的方法是建立在“每一维上的数均是由小到大存储的”
下的。
因此，第一次查找只要找到B[m+1][0]中的m就可以了

Answer 3

int i,j;
for(i=0;i<=m;i++)
{
if(x < B[i][0])
break;
}
for(j=0;i<=n;j++)
{
if(B[i-1][j]==x)
break;
}
最后结果:B[i-1][j]

Answer 4

纠正我的上一个回复int i,j;
for(i=0;i<=m;i++)
{
if(x < B[i][0])
break;
}
for(j=0;j<=n;j++)
{
if(B[i-1][j]==x)
break;
}
最后结果:B[i-1][j]

Answer 5

每一维的概念是如何定义的？
应该是：
   m[i][j]<m[i][j+1]
   m[i][j]<m[i+1][j]
   但是 m[i][j＋1] 和m[i+1][j] 之间是没有关系的那么应该是按照对角线的方式查找下去的

Answer 6

按照对角线找，找到i
使得 m[i][i]<b<m[i+1][i+1]
这样b必然不在左上和右下的区域内
而是位于右上和左下的区域内，在那两个区域内做同样的对角线查找法，即可定位b了

Answer 7

happy__888([顾问团]寻开心)说的有道理
不过我又晕了，到底怎么办啊?

Answer 8

1  1  3  7  9   10
3  4  6  7  11  22
9 10 11 12  13  24
这样的数据定为m=2, n=5是吧。
显然，找到x在哪一行中，比较的次数不超过m。
在一行中找出x，用折半法，或者叫二分法，显然不超过(n+1)/2次。
m + (n + 1) / 2肯定要小于 m + n吧。

Answer 9

用二分法，效率是O(lg(m+n))更快，刚才写了一段：
主要算法就是先把二维表的坐标，转为和一维的线性表一样的处理方式一样。每次总元素的个数（当成一维数组的情况）折半后，再转为二维的i,j坐标计算。#include <stdio.h>
const int MAXROW = 50;
const int MAXCOL = 50;
int main()
{
  int anTest[MAXROW][MAXCOL];
  int i, j, k;  i = j = k = 0;
  for (i = 0; i < MAXROW; ++i)
    for (j = 0; j < MAXCOL; ++j)
      anTest[i][j] = k++;  int nFindNum = 100;
  int front, back;  front = 0;
  back = MAXROW * MAXCOL;
  while ( front <= back ){
    i = ((front + back) / 2) / MAXROW;
    j = ((front + back) / 2) % MAXCOL;    if (anTest[i][j] < nFindNum){
      front = i * MAXCOL + j + 1;
    } else if (anTest[i][j] > nFindNum) {
      back = i * MAXCOL + j - 1;
    } else
      break;
  }
  if ( anTest[i][j] == nFindNum )
    printf("i = %d, j = %d\n", i, j);
  else
    printf("CAN NOT FIND IT\n");
}

Answer 10

SORRY，上面那个二分法查找的效率是：O(lg(m*n))
即使：
如果对每一维都调用一次二分查找，效率只能到：
O( min(n,m) * lg( max(n,m) );  
是不存在O(n+m)的效率算法。死心吧。

Answer 11

设要查找的数为p,从b[0][m+1]开始比较,方向只能往左和往下
如果相比较的数=p,输出
如果相比较的数<p,向下
如果相比较的数>p,向左
如果只有最后一个数没有比较了可能性，那就不要比了，直接输出

Answer 12

#include "stdio.h"#define M 2
#define N 4
int B[M+1][N+1]={1, 2, 4, 10,12,\
                 3, 6, 8, 11,16,\
 5, 7, 9, 13,17};
 
void main()
{
int x=0,y=N;
int p;//要查找的数
int nCount=1;//比较次数 printf("请输入你要查找的数:");
scanf("%d",&p); while(B[x][y]!=p)
{
if(x==M-1&&y==0)break;//不用比了，就只剩一个数了
if(x>M||y<0)break;
++nCount;
if(B[x][y]>p)
--y;
else
++x;

} if(x>M||y<0)
printf("骗我，要找的数根本没有!\n");
else
{
if(x==M-1&&y==0)
printf("你要找的数下标为%d,%d\n",++x,y);
else
printf("你要找的数下标为%d,%d\n",x,y);
printf("查找次数%d\n",nCount);
}
}

Answer 13

设要查找的数为p,从b[0][m+1]开始比较,方向只能往左和往下
----------------------
更正一下，从b[0][N]开始，程序中已经表明

Answer 14

诸位，可以帮忙看一下这里吗？
ttp://community.csdn.net/Expert/TopicView3.asp?id=3841578