面试题：查找有序的二维数组中的元素

summary

:

《剑指Offer》里面看到的一道题，很有意思。

题目

给定一个二维数组，每一行按照从左到右递增排好序了，每一列按照从上到下递增排好序 了，写一个函数，输入这个二维数组和一个整数，判断数组中是否含有这个整数。

分析

抽象问题变具体。考虑下面的二维数组:

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

要查找某个整数，关键是"夹逼"，不断缩小范围，因为是有序的。从哪里开始呢？首先， 左上角和右下角是肯定不行，因为这两个地方不能"夹逼"。以左上角为例，往右边是变 大，往下边也是变大，当要查找的整数比左上角的整数要大时，该往哪边去呢？所以这里 是不行的，同理，右下角也不行。而右上角却可以，主要是因为那里构成了"夹逼"的条 件。比如，要查找某个数，如果比9小，则9所在的列不用看了，因为在9下面的整数都比 9要大，如果比9大，则9所在的行也不用看了，因为在9左边的整数都比9小。同理，左下 角也是可以的。

这样，我们就可以从右上角开始，一步一步缩小范围了。但是，既然二维数组是有序的， 一步一步来是不是太费时了？想想查找有序的数组时可以利用二分查找，那这里也可以！ 但是事实上，二分查找在方形二维数组中效果不是很好。

这是一个经典问题，看 stackoverflow 上的讨论，以及这位大牛提出的 效率高的解法 。

最简单的解法的代码

::: {.code-include lexer="cpp"} ./search-sorted-2d-array.cpp :::

使用了Boost的单元测试框架，链接的时候要加上 -lboost_unit_test_framework 参数。