书中从矩阵的一个边角(如右上角出发),开始查找某数值m,找到后打印m所在的矩阵中位置。假设某一时刻,这时来到了某位置(i,j),如果Data(i,j)<m,将j+1,如果是等于,则m的位置已经找到了;如果大于,则将i+1。按照这样的方式,能够每次减少一行或一列,直到找到目标。这是一道通过比较的方式,查找相应元素的算法。
我想到了两个问题。
- 如果出发时把位置设置在中间,会不会比从右上角快些?
- 如果所比较的数值m换成了序列,如(x(i),y(i))、甚至是三变量(x(i),y(i),z(i)),那还如何从目标中找到答案?
问题一:
如果设置在了中间,那么Data(i,j)<m时,应该向数值递增的右边或下边进行查找,反之,小于则向上边或左边进行查找。虽然每次比较貌似需要比较2次,但是由于处于中间的位置,所以工作量减为1/2。而位于矩阵一角,工作量多一倍,每次比较一次,所以速度应该是一样的(时间复杂度)
问题二:
如果是二变量序列,可以先比较x(i),再比较y(i),多变量序列也是从首位变量到末尾变量的依次比较。这里把二维变量想象成二维平面上,每次比较必然能够移动一格。如果是三维变量则作为立方体,每次比较也必然能够移动一格。结合问题一,在这里,问题已经变了,因为每次只需要比较一次,所以应该从中间开始找,这样能够保证平均情况下工作量是从边界开始的方式的1/2。
(注:这里类比成二维平面、三维立方,并不是说相邻序列其中一个是另一个的某个变量加一或减一这样的关系。仅仅指的是它们严格按照递增、递减的规律。一个区域弄成“实心”、“满”(内部没有空白元素)的这样一种状态)