搜索二维矩阵

来源Leetcode第74题搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。
  示例 1:

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

---

二分查找1

标准的二分查找模板，做这题时先想着确定所在行，最后在确定所在列。
提交的时候遇到了坑，对特殊情况的考虑不周全。

AC的代码如下:

public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0){
        return false;
    }
    int col = matrix[0].length;
    int row = matrix.length;
    int midRow ;
    int leftRow = 0, rightRow = row - 1;
    while (leftRow <= rightRow){
        //确定行号
        midRow = (leftRow + rightRow) / 2;
        if(matrix[midRow][0] <= target && matrix[midRow][col - 1] >= target){
            int midCol = 0;
            leftRow = 0;
            rightRow = col - 1;
            while (leftRow <= rightRow){
                midCol = (leftRow + rightRow) / 2;
                if(matrix[midRow][midCol] == target)
                    return true;
                else if(matrix[midRow][midCol] < target){
                    leftRow = midCol + 1;
                }else {
                    rightRow = midCol - 1;
                }
            }
        }
        else if(matrix[midRow][col - 1] < target){
            leftRow = midRow + 1;
        }else if(matrix[midRow][0] > target){
            rightRow = midRow - 1;
        }
    }
    return false;
}

压缩成为一维数组

来源题解

输入的 m x n 矩阵可以视为长度为 m x n的有序数组。
则row = idx // n ， col = idx % n。

算法：

• 初始化左右序号，left = 0 和 right = m x n - 1。
• While left < right :
  • 选取虚数组最中间的序号作为中间序号: pivot_idx = (left + right) / 2。
    • 该序号对应于原矩阵中的 row = pivot_idx // n行 col = pivot_idx % n 列, 由此可以拿到中间元素pivot_element。该元素将虚数组分为两部分。
    • 比较 pivot_element 与 target 以确定在哪一部分进行进一步查找。

代码如下：

public boolean searchMatrix(int[][] matrix, int target) {
  int m = matrix.length;
  if (m == 0) return false;
  int n = matrix[0].length;

  // 二分查找
  int left = 0, right = m * n - 1;
  int pivotIdx, pivotElement;
  while (left <= right) {
    pivotIdx = (left + right) / 2;
    pivotElement = matrix[pivotIdx / n][pivotIdx % n];
    if (target == pivotElement) return true;
    else {
      if (target < pivotElement) right = pivotIdx - 1;
      else left = pivotIdx + 1;
    }
  }
  return false;
}

筛选法

来源题解

从右上角开始比对，如果大于target，就可以往左前进一列，如果小于target，就往下走一行。

代码如下：

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;
        //从右上角开始，比较target与右上角的数据的大小，如果大于target，就可以往左进一行，如果小于target，就可以往下走一行
        while(i<m && j>= 0){
            if (matrix[i][j] > target){
                j--;
            }else if (matrix[i][j] < target){
                i++;
            }else {
                return true;
            }
        }
        return false;
    }