LeetCode | 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.

  分析

  原來做過：九度Online Judge | 劍指offer | 題目1384：二維數組中的查找，文中給出了大牛的鏈接。

  解法1：二分法

  解法2：從右上或左下開始搜索，以右上為例，如果被搜索的元素大於target就減橫坐標，如果小於target就減縱坐標，否則就是相等返回true

  解法1

  public class SearchA2DMatrix {
  	public boolean searchMatrix(int[][] matrix, int target) {
  		if (matrix == null || matrix.length == 0) {
  			return false;
  		}
  		int M = matrix.length;
  		int N = matrix[0].length;
  		int low = 0;
  		int high = M * N - 1;
  		while (low <= high) {
  			int mid = low + (high - low) / 2;
  			if (matrix[mid / N][mid % N] == target) {
  				return true;
  			} else if (matrix[mid / N][mid % N] > target) {
  				high = mid - 1;
  			} else {
  				low = mid + 1;
  			}
  		}
  		return false;
  	}
  }

  解法2

  public class SearchA2DMatrix {
  	public boolean searchMatrix(int[][] matrix, int target) {
  		if (matrix == null || matrix.length == 0) {
  			return false;
  		}
  		int M = matrix.length;
  		int N = matrix[0].length;
  		int i = 0;
  		int j = N - 1;
  		while (i <= M - 1 && j >= 0) {
  			if (matrix[i][j] == target) {
  				return true;
  			} else if (matrix[i][j] > target) {
  				--j;
  			} else {
  				++i;
  			}
  		}
  		return false;
  	}
  }