查找算法：在双重排序的数组中进行快速查找

假设A是一个n\*n的二维数组。它的行和列都按照升序排列，给定一个数值x，设计一个有效算法，能快速在数组A中查找x是否存在。同时考虑一个算法效率的下界，也就是无论任何算法，它的时间复杂度都必须高于某个给定水准。

这道题难度不大，看到排序数组时，我们就应该本能的考虑到使用二分查找。我们先看一个具体实例，假设有一个符合条件的二维数组如下：


最简单的方法是，循环遍历整个二维数组，依次查找给定元素是否与给定元素一样，当然这么做的算法复杂度是O(n^2)，因为没有理由到排序特性，因此效率不高。

由于数组的行和列都已经按升序排好，我们可以利用这个性质加快查找速度。假设在给定例子中，我们要查找数值6.5，我们首先以行为主，在一行范围内进行折半查找，此时发现第一行的末尾元素小于6.5，因此我们继续考虑第二行。在第二行中，折半查找到7时，7比6.5大，此时根据行和列都升序排列的条件，我们可以忽略掉7开始的子矩阵，也就是[7,8,11,12,15,16]，由此一下子就排除掉无需考虑的一大堆元素。

由此我们可以归纳出基于折半查找的算法步骤：

1， 从当前行开始折半查找，直到找到给定数值元素或是找到一个比查找数值小的最大元素时停止，假设该元素位于第j列。

2，由于矩阵元素按照列进行升序排列，因此我们可以在第j列元素中进行折半查找，直到找到给定数值元素，或是大于给定元素的最小元素为止，假设该元素位于第i行

3，在第i行中的[0,j-1]范围内的元素中折半查找。

总结一下，折半查找时，有两种查找方向，一个是横向查找，也就是在一行内查找，在行内查找时，停止的标志是找到给定元素，或者是找到一个比给定元素小的最大元素。另一个是竖直查找，它停止的标准是找到给定元素，或是找到一个比它大的最小元素时停止，之所以设立这个标准，是因为行和列升序排列的规律。

如果在一行内查找到下一个元素比给定值大时，我们便无需考虑后面元素，因为按照升序排列的原则，后面的元素绝对比要查找的元素大，同时也无需考虑同一行内，比给定值小的最大元素前面的元素，因为他们一定比给定值小，所以此时我们需要在竖直方向上查找。

在竖直方向上查找时，如果元素值比给定数值小，那么该元素同行内左边元素都可以无需考虑，如果元素比给定值大，那么位于元素下方的元素都可以不用考虑，如果找到一个比给定数值大的最小元素时，如果数组存在给定数值大小相同的元素，那么一定位于该元素的左边子矩阵，因此此时可以在该元素所在行左边的元素中折半查找。

例如给定数值10，我们在上面二维矩阵中查找，首先我们在第一行折半查找，找到第一行最后一个元素4，然后在4所在列折半查找，找到比10大的最小元素时12，然后我们在12所在的行内折半查找，于是就能找到元素10.

由于我们一次折半查找时，至少能排除掉一行或一列，由于每次折半查找的时间复杂度为lg(n)，因此总的时间复杂度是O(n\*lg(n))。

其实我们还有更好的方法。那就是不用折半查找，只需要比对每一行的最后一个元素，例如从第一行开始，我们先比较A[0][n-1]，如果A[0][n-1]>x，此时我们可以排除掉最后一列，然后比较A[0][n-2]。如果A[0][n-2] < x，此时我们可以排除掉当前行，然后考虑A[[1][n-2]，如此递归下去，由于我们每次比较都排除一行或一列，因此经过最大n次比较我们就可以得出答案，而该算法的复杂度是O(n)。

这个问题另一个难点在于确立算法时间复杂度的下界，也就是无论任何算法，它的时间复杂度都必须高于给定标准。我们看一个特别的排序矩阵，假设要查找的元素是x,那么对于矩阵：


也就是我们把矩阵对角线上元素全部设置成x-1,它正下方元素设置成x+1，那么无论何种算法，它都必须要访问这些元素。因为假设存在一个算法，它不访问这些元素中的某一个，那么我们可以把不访问的那个元素换成x，同时矩阵的行和列递增性都不会变，而且该x在矩阵中是唯一的，因此该算法在找到给定x前就会退出，因此它会返回错误结果，由此无论任何算法，对于给定上面矩阵，它都必须访问这些元素，而元素的数量总共有2n-1个，所以无论给定任何算法，它的下界都是2n-1。