搜索二维矩阵

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

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

示例 1：


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


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
输出：false
示例 3：

输入：matrix = [], target = 0
输出：false
 

提示：

m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

笨方法 先对行二分查找，再对列二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int h = matrix.length;
        int w = matrix[0].length;
        int low = 0, heigh = h;

        while (low <= heigh - 1) {//对行进行二分查找
            int mid = (low + heigh) / 2;
            if (mid < h) {
                if (matrix[mid][0] < target) {
                    low = mid + 1;
                    if (matrix[mid][w - 1] >= target) {
                        low = mid;
                        break;
                    }
                } else if (matrix[mid][0] > target) {
                    heigh = mid - 1;
                } else {
                    return true;
                }
            } else {
                heigh--;
            }
        }

        if (target > matrix[h - 1][w - 1] && low > 0) {
            low--;
        }

        int left = 0, right = w;
        while (left <= right) {//对列进行二分查找
            int mid = (left + right) / 2;
            if (mid < w) {
                if (matrix[low][mid] < target) {
                    left = mid + 1;
                } else if (matrix[low][mid] > target) {
                    right = mid - 1;
                } else {
                    return true;
                }
            } else {
                right--;
            }

        }
        return false;
    }
}

官方思路

将二维数组转化为一维数组然后对整个数组进行二分查找
每个中间的节点的行列值为：

0. mid=(left+right)/2
1. w=matrix[0].length
2. row=mid/w
3. col=mid%w

class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int h = matrix.length;
        int w = matrix[0].length;
        int left = 0, right = h * w - 1;
        //将二维数组转一维
        //选取虚数组最中间的序号作为中间序号: pivot_idx = (left + right) / 2。
        //该序号对应于原矩阵中的
        // row = pivot_idx // w 行
        // col = pivot_idx % w 列,
        // 由此可以拿到中间元素pivot_element。该元素将虚数组分为两部分。
        while (left <= right) {
            int mid = (left + right) / 2;
            int row = mid / w;
            int col = mid % w;

            if (matrix[row][col] < target) {
                left = mid + 1;
            } else if (matrix[row][col] > target) {
                right = mid - 1;
            } else {
                return true;
            }

        }
        return false;
    }
}

官方题解

class Solution {
  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;
  }
}

参考文献

官方题解

赏

谢谢你请我吃糖果

微信