一、题目

　　1、审题

　　

　　2、分析

　　　　给出一个二维数组，每一行的元素、每一列的元素均有序。在此数组中查找 target 元素。

 

二、解答

　　1、思路

　　　　方法一、

　　　　　　在每一行中用二分查找法。

public boolean searchMatrix(int[][] matrix, int target) {                int rows, cols;        if(matrix == null || (rows = matrix.length) == 0 || (cols = matrix[0].length) == 0)            return false;                int row = 0;        while(row < rows) {            int start = 0, end = cols - 1;            if(matrix[row][0] > target)                return false;            if(matrix[row][end] < target) {                row++;                continue;            }            while(start <= end) {                int mid = (end - start) / 2 + start;                if(matrix[row][mid] == target)                    return true;                else if(matrix[row][mid] < target)                    start = mid + 1;                else                    end = mid - 1;            }            row++;        }        return false;    }

 

　　方法二、

　　　　从二维数组的右上角开始向前、向下定位：

　　　　①、若 target 小于当前元素，则 target 不可能在当前列，因为列向下为升序。

　　　　②、若 target 大于当前元素，则 target 不可能在当前行，因为当前行为升序。

public boolean searchMatrix(int[][] matrix, int target) {        int rows, cols;        if(matrix == null || (rows = matrix.length) == 0 || (cols = matrix[0].length) == 0)            return false;                // 从右上角开始查找        int row = 0, col = cols - 1;        while(col >= 0 && row < rows) {            if(target == matrix[row][col])                return true;            else if(target < matrix[row][col])                col--;            else if(target > matrix[row][col])                row++;        }        return false;    }