这样的面试题，你会吗？（有奖）

axjlq

二维数组那个，应该从对角线去比较，这样才比较省

axjlq

回复 78# hbmhalley


    对于你的问题，是这样的，首先对角线是159，3应在这条对角线上面，所以，继续看对角线26，还是上方，找到3，不知道这样理解对不对

hbmhalley

回复 81# axjlq


    那要是找4呢

冰水1101

思路：
“在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。“
我们可知这个二维数组(a[m][n])以及它内部任意一个二维数组 的 左上角的数(a[0][0])都是最小的，右下角的数(a[m-1][n-1])都是最大的。
做法：
首先设我们要查找的数为x,二维数组(a[m][n])，且行小于列(m<n)。其中count初始值为1，
（1）如果要查找的数小于左上角的数，或是大于右下角的数，return false。
（2）如果等于左上角的数，或是等于右下角的数，return ture。
（3）对最后一列进行折半查找,找到第一个大于x的数a[ii][n-count]   ((ii>=0)&&(ii<m))
（4）对最后一行进行折半查找,找到第一个大于x的数a[m-count][j]   ((j>=0)&&(j<n))
（5）数组的范围缩小到a[ii][j] 到a[m-count-1][n-count-1]，count++，从（1）开始进行

稍候上传代码

谢谢hbmhalley 的指正。（欢迎再来指正，谢谢）
更改具体做法：
首先设我们要查找的数为x,二维数组(a[][])，且行小于列(m<n)。其中count初始值为1，
（1）如果要查找的数小于左上角的数，或是大于右下角的数，return false。
（2）如果等于四个角的数（左上角、左下角、右上角、右下角），return ture。
（3）如果第一列的最后一个数小于x,则跳到（4）。否则，对第一列折半查找,找到x 则return ture，否则定位到这一列里比x小但和x最近的数a[ii][0] 。
（4）如果第一行的最后一个数小于x,则跳到（5）。否则，对第一行折半查找,找到x 则return ture，否则定位到这一行里比x小但和x最近的数a[0][j] 。
            （ps:经过（4）以后，数组中我们的查找范围就缩小到从a[0][0]到a[ii][j] i行j列的数组了）
（5）对j列进行折半查找,找到x 则return ture，否则找到第一个大于x的数a[p][j]   ((p>=0)&&(p<ii))
（6）对i行进行折半查找,找到x 则return ture，否则找到第一个大于x的数a[ii][q]   ((q>=0)&&(q<j))
                  （ps:经过（6）以后，数组的范围缩小到a[p][q] 到a[ii][j]
（7）重复（1）开始进行

hbmhalley

回复 83# 冰水1101


    1 2 3
    4 5 6
    7 8 9

    Query = 5

    怎么找

hbmhalley

话说大家在回复之前看看

    1 2 3
    4 5 6
    7 8 9

这组萌死人的数据里 有没有一个数会萌翻你的log
..

冰水1101

回复 84# hbmhalley


    谢谢hbmhalley 的指正。（欢迎再来指正，谢谢）
更改具体做法：
首先设我们要查找的数为x,二维数组(a[][])，且行小于列(m<n)。其中count初始值为1，
（1）如果要查找的数小于左上角的数，或是大于右下角的数，return false。
（2）如果等于四个角的数（左上角、左下角、右上角、右下角），return ture。
（3）如果第一列的最后一个数小于x,则跳到（4）。否则，对第一列折半查找,找到x 则return ture，否则定位到这一列里比x小但和x最近的数a[ii][0] 。找到4
（4）如果第一行的最后一个数小于x,则跳到（5）。否则，对第一行折半查找,找到x 则return ture，否则定位到这一行里比x小但和x最近的数a[0][j] 。跳到（5）
            （ps:经过（4）以后，数组中我们的查找范围就缩小到从a[0][0]到a[ii][j] i行j列的数组了）
此时数列是
1     2     3
4     5     6

（5）对j列进行折半查找,找到x 则return ture，否则找到第一个大于x的数a[p][j]   ((p>=0)&&(p<ii))   找到6
（6）对ii行进行折半查找,找到x 则return ture，否则找到第一个大于x的数a[ii][q]   ((q>=0)&&(q<j))   找到5
                  （ps:经过（6）以后，数组的范围缩小到a[p][q] 到a[ii][j]
（7）重复（1）开始进行

------------------------------------------------
为什么方括号中间写i是斜体 只能写[ii]了 所以又重新贴了一下

hbmhalley

回复 87# 冰水1101


    算法没问题 但效率不高于线性啊

    思路是不错的，但和22L是一个想法，即：每次切掉一定大于或小于的行或列，只不过22L每次用单位时间切一行，你用log的时间切不知道多少行
    但这个题无论如何都有一个“左下与右上”的矛盾，如果不能直视这个问题，你的log也只作为小伎俩来使用，还有可能适得其反，比如：

1. 
   
2. OOOOX
   
3. OOOXX
   
4. OOGXX
   
5. OOXXX
   
6. OXXXX
   
7. // O==-INF, X==INF, G(goal)==INF/2
   

复制代码

你的行与列还是分开搞的，导致用log的时间也还是只能切掉一行一列

donxj1979

回复 1# 无风之谷

青蛙跳台阶问题2：
若跳N-1级台阶有m种跳法，则跳N级台阶就有（2m+1）种跳法。
首次发帖，不对请指正！