经典面试题15 - 马鞍式搜索

像不像马鞍?

问题
在一个整数组成二维数组内，元素从左到右，从上到下都是递增的。
如何判断任意一个目标数值是否在数组内？

数组样例: 
//元素从左到右，从上到下都是递增的
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

解答

先来看基本的思路如下：

1. 从数组的左下角开始搜索。
2. 如果目标数值比当前值小，那么它如果在数组存在一定在当前值上方，向上移动一个元素。(因为当前值右面的数值都是大于当前值的)
3. 如果目标数值比当前值大，那么它如果在数组存在一定在当前值右面，向右移动一个元素。(因为当前值上面的数值都是小于当前值的)
4. 回到第二步，再次开始搜索。

对于一个N x M的数组，上述思路的时间复杂度是O(N+M)。

上面的思路针对M或N都是较大的数值，如果N或M的数值较小，可以使用二分查找来提升时间效率，如M=1的时候。

这种思路被称为 Saddleback Searc - 马鞍式搜索，更多请参看这里(传送门)

基于此方法结合二分查找还有一种改进思路，其时间复杂度为O(N * log(M/N))，细节参看这里传送门 - 英文版。

推荐阅读

经典面试100题 - 持续更新中