搜索二维矩阵 II：从右上角走
每行从左到右递增，每列从上到下递增。站在右上角：当前数太大就往左丢掉这一列，太小就往下丢掉这一行。
从 (0, n−1) 出发。当前值大于 target 则列号减一（这一列往下只会更大）；小于 target 则行号加一（这一行往左只会更小）。相等即找到，走出边界即没有。时间 O(m+n)，空间 O(1)。
给你一个矩阵，每一行从左到右递增，每一列从上到下递增。判断 target 在不在里面。行与行之间没有「上一行末尾小于下一行开头」这种全局顺序，不能当成一整条有序数组对半切。
主例五行五列，第一行 1 4 7 11 15，第二行 2 5 8 12 19，后面三行同样向右、向下变大。target = 5，在第二行第二列，应当返回 true。
每行二分是 O(m log n)，能做对。本文要回答：为什么右上角一步就能丢掉整行或整列，以及主例从 15 走到 5 中间经过哪些格子。
一步丢掉整行或整列
第一直觉是每行扫一遍，最坏看完所有格子。或者每行二分，主例五次二分也能找到 5。这两种都没有用上「列也递增」。另一种错觉是从左上角出发：左上角往右、往下都在变大，当前数比 target 小的时候，两条路都可能藏着答案，不知道该丢哪一边。
缺的是一个比较完就能排除一片的起点。右上角 (0, n-1) 是拐点：它是这一行最大的数，也是这一列最小的数。当前值大于 target，这一列往下更大，整列都不可能，列号减一。当前值小于 target，这一行往左更小，整行都不可能，行号加一。每次比较，行数加列数减一，最多走 m+n 步。
左下角对称：它是这一行最小、这一列最大，大了往上、小了往右，同样能走通。左上、右下两头都单调同一方向，一步无法排除一行或一列，不要从那里开局。
用手走主例，target=5。起点 (0,4) 是 15，15>5，整列 15、19、22、24、30 都更大，往左；演示第一帧停在这里。继续向左经过 11、7，都比 5 大，落到 (0,1) 的 4，这是演示第二帧。
4<5，第一行左边只剩更小的 1，整行丢掉，往下走到 (1,1)。这里是 5，命中，返回 true。中间 11、7 两步演示省略了，轨迹仍是只向左或向下，没有折返。
若 target 不在矩阵里，指针会在某次减列或加行之后走出上边界或左边界，循环结束返回 false。不要在中间格子又往右又往上，那样会把已经排除的区域捡回来，最坏退化成全表扫描。每行二分在行很长、行数很少时也可以，但主例这种接近方阵的输入，走拐点更省比较。
单调走廊右上角一行一列的单调方向相反，所以比较一次就能决定丢掉哪一片。路径只向左或向下，不必回溯。左下角是同一条走廊的另一头入口。
Go：右上角 Z 字形
func searchMatrix(matrix [][]int, target int) bool {m, n := len(matrix), len(matrix[0])r, c := 0, n-1for r < m && c >= 0 {if matrix[r][c] == target {return true} else if matrix[r][c] > target {c--} else {r++}}return false}
1r、c 从右上角起步。循环条件是还在矩阵里：行向下不越界，列向左不越界。
2大于 target 只减 c，小于只加 r。主例 15→11→7→4 都是减 c，4 到 5 是加 r。
3走出边界还没相等，就是没有。不要在分支里同时改 r 和 c。
总结
从右上角走：大了丢列往左，小了丢行往下。主例 15 经 4 落到 5。
- 左上角两条路都变大，一步排除不了一片。右上角或左下角才是拐点。
- 主例路径是 (0,4)→…→(0,1)→(1,1)，只向左或向下。
- 最多 m+n 步。越界即不存在。LC74 多了全局有序，才能整表二分。