今天开始刷剑指offer，首先是关于数组的问题，原题目链接：二维数组中的查找问题。
我们把题目在此处重新复述一遍：
题目描述：
在一个二维数组中（每一个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否有该整数。
题目分析：
据题可以得到如下几个条件：1.二维数组是有序的；2.从该数组中查找某个数是否存在。
如果只看第2个条件，那肯定会直观的想到挨个取出数组中的每个元素，比较是否存在。很明显，这种方法不是最好的；因为如果数组中不存在该数值，则需要把所有的元素都取出来比较。
那么对于有序的数组，我们可以进行哪些查找操作呢？
1.如果是一维数组，那肯定是要用效率最高的二分查找；那么在二维数组中可不可以用二分呢？该怎么用呢？
2.直接考虑二维数组，有没有什么好的方法呢？
先看一下二分方法
对于一维有序递增数组，二分便是拿出中间位置的元素比较；若该数值大于中间元素；说明该数值不会出现在前一半位置；所以可能在后一半元素中，对后一半元素依然使用该方法，直到只剩下一个元素为止。
二维有序数组如何使用二分？
我们可以简单的把二维数组当作多个一维有序数组；分别对每个一维数组使用二分查找即可。此种方法的实现代码如下：
//使用二分 public boolean Find(int target, int [][] array) { // 二维数组有m行n列 int m = array.length; int n = array[0].length; // 数组需非空 if(m <= 0 || n <= 0){ return false; } // 目标数也不能越界 if(target < array[0][0] || target > array[m-1][n-1]){ return false; } // 对m行分别使用二分 for(int i=0; i<m; i++){ int left = 0; int right = n-1; int middle = 0; while(left <= right){ middle = (left + right) / 2; if(target < array[i][middle]){ right = middle - 1; }else if(target >array[i][middle]){ left = middle + 1; }else{ return true; } } } return false; }
此代码在牛客网上运行时间为149ms。
再看一下直接考虑二维数组
上面的算法虽然还不错，但是该算法基本是对每一行都进行二分查找操作；这样肯定不是最好的。那么再来观察一下数组的特性：
1.从左到右是递增的
2.从上到下是递增的
再观察一下图形：
仔细观察可以发现，左下角的元素，向右是增加，向上是减小；右上角的元素，向下是增加，向左是减小。
假如选择这两个特殊点作为起始比较点，那么比较一次就可以直接排除一行或者一列元素。
以左下角为例，如果目标数值大于6，则第1列不可能有该目标数值；那么待比较数组就变成了3行3列。再选取新待比较数组的左下角元素7；若目标数值小于7，则最后一行不可能有该目标数值。新的待比较数组又变成了2行3列。持续下去，直至新的待比较数组不存在或者找到该目标元素为止。
此种方法的实现代码如下：
public boolean Find(int target, int [][] array) { // 二维数组有m行n列 int m = array.length; int n = array[0].length; // 数组需非空 if(m <= 0 || n <= 0){ return false; } // 目标数也不能越界 if(target < array[0][0] || target > array[m-1][n-1]){ return false; } // 从左下角开始比较 int row = m-1; int col = 0; while(row >= 0 && col < n){ if(target > array[row][col]){ col++; }else if(target < array[row][col]){ row--; }else{ return true; } } return false; }
此代码在牛客网上运行时间为117ms。
目前为止只想到这两种方法，更高效的暂时还没想到。先这样吧，继续刷起。