力扣74——搜索二维矩阵

这道题主要就是利用二分查找，将矩阵做变换进行优化。

原题

编写一个高效的算法来判断 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

原题url：https://leetcode-cn.com/problems/search-a-2d-matrix/

解题

二分查找

既然是已经排好序的，那么我第一想到的就是二分查找了。每次进行对半查找，时间复杂度O(log(mn))，应该还是很高效。

我准备将查找分成两部分，第一是二分查找找到 target 在哪一行，然后从那一行再利用二分查找找到 target 在这一行的哪个位置。

让我们来看看代码：

class Solution {

    // 总行数
    int row;
    // 总列数
    int col;

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

        row = matrix.length;
        col = matrix[0].length;
        // 利用二分法查询
        return binarySearchMatrix(matrix, 0, matrix.length - 1, target);
    }
        
        /**
          * 查找这是矩阵的哪一行
          */
    public boolean binarySearchMatrix(int[][] matrix, int left, int right, int target) {
        if (left > right) {
            return false;
        }
        if (left == right) {
            int[] array = matrix[left];
            if (target < array[0] || target > array[col - 1]) {
                return false;
            }
                        
                        // 从数据中心查找
            return binarySearchArray(array, 0, col - 1, target);
        }

        int middle = (left + right) / 2;
        int[] middleArray = matrix[middle];
        if (middleArray[0] > target) {
            return binarySearchMatrix(matrix, left, middle - 1, target);
        } else if (middleArray[col - 1] < target) {
            return binarySearchMatrix(matrix, middle + 1, right, target);
        } else {
            return binarySearchArray(middleArray, 0, col - 1, target);
        }
    }
        
        /**
          * 查找这是数组中的哪个位置
          */
    public boolean binarySearchArray(int[] array, int left, int right, int target) {
        if (left > right) {
            return false;
        }
        if (left == right) {
            return array[left] == target;
        }

        int middle = (left + right) / 2;
        if (array[middle] > target) {
            return binarySearchArray(array, left, middle - 1, target);
        } else if (array[middle] == target) {
            return true;
        } else {
            return binarySearchArray(array, middle + 1, right, target);
        }
    }
}

提交OK，其执行用时：1 ms，内存消耗：38.3 MB。

优化

虽然解题成功，且效果不错，但总感觉这样写的太过。因为我将二维数组的查找分为两种情况，如果以后变成三维、四维数组，岂不是代码更长？其实这种查找都是利用的同一种思想——二分查找，那我们是否可以将其进行合并呢？

可以的，我们可以将二维数组拉长。拉成1层后，就可以直接用一维数组中的二分查找了。

让我们看看代码：

class Solution {

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

        int col = matrix[0].length;
        // 将二维数组拉成一维数组，利用二分法解决
        int left = 0;
        int right = matrix.length * col - 1;
        while (left <= right) {
            // 计算中间数的下标和值
            int middleIndex = (left + right) / 2;
            int middleVal = matrix[middleIndex / col][middleIndex % col];
            if (middleVal == target) {
                return true;
            }

            if (middleVal < target) {
                left = middleIndex + 1;
            } else {
                right = middleIndex - 1;
            }
        }

        return false;
    }
}