上学期，我把这个问题摆在家庭作业上，两个我认为是中等水平的学生提出了一个非常优雅，简单和（可能）最优的算法，这让我感到惊讶：

Find(k, tab, x, y)
  let m = tab[x][y]

  if k = m then return "Found"
  else if k > m then
    return Find(k, tab, x, y + 1)
  else
    return Find(k, tab, x - 1, y)

该算法在每次调用时都消除了一行或一列（请注意，它是尾部递归的，并且可以转换为循环，从而避免了递归调用）。因此，如果您的矩阵为n * m，则算法以O（n +
m）执行。这个解决方案比二分法搜索更好（解决该问题时我期望的解决方案）。

编辑 ：我修复了一个错字（在递归调用中k变为x），而且，正如克里斯指出的那样，最初应使用“右上角”来调用它，即Find（k，tab，n，1），其中
n 是行数。