[Java]二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。《剑指offer面试题3》

public class TwoDimensionalArray {
public static void main(String[] args) {
int column = 5;
int row = 5;
int [][] A = new int[column][row];
for (int i = 0 ; i < column ; i++){
for (int j = 0; j< row; j++){
                A[i][j] = i + j;
                System.out.print(A[i][j]);
            }
            System.out.println();
        }
        TwoDimensionalArray array = new TwoDimensionalArray();
        System.out.println(array.find(A, column, row, 9));
    }

private boolean find(int [][] matrix, int rows, int columns, int target){
        boolean found = false;
if (matrix != null && rows > 0 && columns > 0){
for (int row = 0, column = columns - 1; row < rows && column >= 0; ){
if (matrix[row][column] == target){
                    found = true;
break;
                } else if (matrix[row][column] > target){
                    column--;
                } else {
                    row++;
                }
            }
        }
return found;
    }
}

分析：暴力的二维数组遍历查找时间复杂度是O(n2), 从矩阵右上开始遍历可以降低到O(n), 如果考虑单行或者单列matrix，就包含了一维数组查找，二分法可log(n)时间内得到结果。