我目前正在阅读 Richard Bird 和 Jeremy Gibbons 合着的 Algorithm Design with Haskell，Saddleback search算法在第四章中给出了二分查找后，给出的动机问题是:
给定 f:N x N -> N 在两个参数中都严格递增，并且值 t 找到所有对 (x,y) 这样 f(x,y)=t。
第一个定义由 search f t =[(x,y) | x ← [0..t],y ← [0..t],t == f(x,y)]，从左下角的原点开始向右上角搜索角，(索引从下到上，从左到右递增)，然后本书继续进行改进。
第二个定义由 search f t =[(x,y) | x ← [0..t], y ← [t,t −1..0],t == f(x, y)],
书中引用了这个定义
“第一个改进是从左上角开始，而不是从左下角开始”，然后本书继续进行，直到它变成 Theta(m+n) 对于维度为 n x m.
最终的算法是这样的
search f t = searchIn (0,t)
where searchIn (x, y) | x>t ∨ y<0 =[]
| z<t = searchIn (x+1, y)
| z == t = (x, y):searchIn (x+1, y−1)
| z>t = searchIn (x,y−1)
where z = f(x,y)
为什么会这样？从原点(0,0)开始有什么问题？，还有 为什么 x 坐标增加而 y 坐标减少，反之亦然(我在 leetCode 上看到 x 减少，y 增加)，为什么不让两个坐标都朝增加的方向移动？
最佳答案
问题的典型输入如下所示:
黑色像素表示大于 t 的值，白色较小，灰色等于。我们的目标是找到所有的灰色点。理想情况下，要进行此搜索，我们只想沿着黑色和白色之间的边界行走。唯一的问题是我们不知道边界从哪里开始，所以我们需要搜索甚至知道在哪里搜索。如果我们从左下角开始，我们将不得不这样做:
第一步是找到边界，我们可以从左下角向上扫描，直到找到它。但是……我们必须掉头!搜索的其余部分，我们继续向下和向右。所以我们必须把我们的搜索分成两个阶段，一个是找到边界，另一个是跟随它。但是，如果您从左上角开始...
这一次，我们不必掉头，这意味着我们可以重用我们用于跟踪其余边界以首先找到边界的相同代码!
这回答了“为什么不从原点开始”。另一个问题，“为什么不在一个方向上增加而在另一个方向上减少”，好吧......你可以。这是一个几乎相同的问题，几乎相同的算法将解决它。
关于algorithm - 鞍背搜索起点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68854526/