重新解读剑指Offer之3题 二维数组中的查找

首先描述一下问题，存在一个二维数组，每一行数据从左到右递增，每一列数据从上到下递增。给定一个需要查找的参数，问在这个参数是否在二维数组中。原书中的解法是从二维数组的左下角或者右上角出发，一次排除一行或者一列，逐渐缩小范围，如图1所示，这种解法的最坏时间复杂度是O(m+n)，其中m，n分别是二维数组的行数与列数，该算法实现非常简单也容易理解。以左下角为例，当需要寻找的数据比当前数据大，则向右寻找，排除当前列，若小，则向上寻找，排除当前行，否则直接返回 除此之外，当然可以一行一行的进行二分查找，最坏时间复杂度是O（m*Lg[n]）,也可以一列一列的进行二分查找，最坏时间复杂度是O（n*Lg[m]）,这两种时间复杂度还是有一定区别的，可以证明当2<=m，m’<’n时，O（m*Lg[n]）<=O（n*Lg[m]）,这与我们的直觉是一致的。 接下来的这种解法与原书作者的想法属于殊途同归，如下图2所示，理想情况下的一个m x m的二维数组，其对角线上的值是大于该点左上角的全部值的，利用这一属性，也可以达到快速排除某些区域的效果，只不过每次排除的区域不是线性变化的，当最终区域为一列一行时，便可以利用二分查找解决了。但是对于非理想的行数与列数不相等的二维数组该怎样处理呢？ 答案如图3所示。 根据行列数目较小的一个裁剪出一个m x m的规则矩阵与一个不规则矩阵，m x m的规则矩阵的寻找方式已经在上面解释了，对于非规则矩阵的处理就是递归调用自己，裁剪出规则矩阵，那么递归的终止条件是啥呢？当不规则矩阵是一行式或者一列式时转入二分查找便可以结束递归了。 ok,上代码，，， 由于对markdown不太熟悉还是Bug，粘贴源代码时编辑器跳来跳去，所以将源代码贴到下一篇博文中了。