74. Search a 2D Matrix

题目

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

思路

观察：

1. 比较每行最后的一个数
2. 如果每行最后一个数比target大，则删除最后一列；
   如果每行最后一个数比target小，则删除本行

代码

package array;

/**
 * Created by liqiushi on 2018/3/19.
 */
public class Search2DMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int column = 0;
        if (row > 0) {
            column = matrix[0].length;
        }

        for (int r = 0, c = column - 1; (r <= row - 1) && (c >= 0); ) {
            if (matrix[r][c] > target) {
                c--;
            } else if (matrix[r][c] < target) {
                r++;
            } else {
                return true;
            }
        }
        return false;
    }
}

分治思路

1. 以图形中点开始分
2. 如果中点比target小，则根据杨氏矩阵的规律，去掉左上角，递归右边和下边
3. 如果中点比target大，去掉右下角

代码

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int column = 0;
        if (row > 0) {
            column = matrix[0].length;
        }
        return find(matrix, 0, 0, row - 1, column - 1, target);
    }

    private boolean find(int[][] matrix, int x1, int y1, int x2, int y2, int target) {
        if (x1 > x2 || y1 > y2) {
            return false;
        }
        int midx = (x1 + x2) >> 1;
        int midy = (y1 + y2) >> 1;
        if (target < matrix[midx][midy]) {
            return find(matrix, x1, y1, midx - 1, y2, target) || find(matrix, midx , y1, x2, midy - 1, target);
        } else if (target > matrix[midx][midy]) {
            return find(matrix, x1, midy + 1, x2, y2, target) || find(matrix, midx + 1, y1, x2, midy, target);
        } else {
            return true;
        }
    }