题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
分析
例如二维数组arr = [ [1,2,3,4], [5,6,7,8], [9,10,11,12] ],target=7,如果按照常规的查找,从arr[0][0]开始,那么target>arr[0][0],arr[0][1]和arr[1][0]都大于arr[0][0],接下来该怎么办呢?这就陷入了一个无法进行下去的局面。
所以,要在一个数组中查找某target,则有办法确定一个唯一的方向,即下一步该向左还是向右、向上还是向下。
观察题目,二维数组的每一行都按照从左向右递增,每一列都按照从上到下递增,那么如果从二维数组的左下角开始,就可以保证向上的都是小的,向右的都是大的,过程就可以进行下去了。
代码实现
function Find(target, array) { if(array === null) return false; var curRow = array.length-1; var curCol = 0; while(curRow >=0 && curCol < array[0].length){ if(array[curRow][curCol] === target) return true; else if(array[curRow][curCol] > target) curRow--; else curCol++ } return false; }