力扣-搜索二维矩阵

这篇具有很好参考价值的文章主要介绍了力扣-搜索二维矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

74. 搜索二维矩阵

这道题和在一维数组中查找目标值很像，不过这里的数组变成了二维数组。
在解这道题之前先讲一下怎么在升序一维数组里面用二分查找法找不大于某个目标值(target)的最大索引。例如在数组nums = {1, 3, 5, 7, 9}里面要查找目标值 target = 6，应返回的索引为 2。

// 查找 nums 中小于等于 target 的最大下标，例如当 nums = {1, 3, 5, 7}, target = 4 时，要返回的坐标为1
    public int findRow (int[] nums, int target){
        int left = 0, right = nums.length - 1;
        // maxIndex 用于保存最终要返回的索引值。
        int maxIndex =  -1;
        int mid = -1;
        while (left < right){
            mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target){
                maxIndex = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return maxIndex;
    }

思路

因为该二维数组中每行元素都为升序，每列元素也都为升序，因此可以通过两次二分查找来求解。第一次二分法找到对应的行的位置，第二次二分查找找到对应列的位置。

public boolean searchMatrix(int[][] matrix, int target) {
        boolean flag = false;

        // 边界条件
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length, col = matrix[0].length;

        // 找行的位置
        int left = 0, right = row - 1;
        // 保存要找的元素在哪一行
        int maxRowIndex = -1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            // 找到
            if (matrix[mid][0] <= target){
                maxRowIndex = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        // 找列的位置
        if (maxRowIndex == -1) {
            return false;
        }
        else{
            int leftCol = 0, rightCol = col - 1;
            int midCol = 0;
            while (leftCol <= rightCol){
                midCol = leftCol + (rightCol - leftCol) / 2;
                if (matrix[maxRowIndex][midCol] == target) {
                    flag = true;
                    break;
                }
                else if (matrix[maxRowIndex][midCol] < target){
                    leftCol = midCol + 1;
                }
                else {
                    rightCol = midCol - 1;
                }
            }
        }

        // 找列的位置
        return flag;
    }

将代码封装一下。

public boolean searchMatrix(int[][] matrix, int target) {
        boolean flag = false;

        // 边界条件
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int maxIndex = searchRow(matrix, target);
        if (maxIndex == -1) {
            return false;
        }
        return searchCol(matrix, target, maxIndex);

    }

  // 寻找对应行的位置
 public int searchRow (int[][] nums, int target){
      int rows = nums.length, cols = nums[0].length;

      int left = 0, right = rows - 1;
      int mid = -1;
      int maxIndex = -1;
      while (left <= right){
          mid = left + (right - left) / 2;
          if (nums[mid][0] <= target){
              maxIndex = mid;
              left = mid + 1;
          }
          else {
              right = mid - 1;
          }
      }

      return maxIndex;
 }

 // 在每一行中查找对应列的位置
 public boolean searchCol (int[][] nums, int target, int maxIndex){
      int left = 0, right = nums[0].length - 1;
      int mid = -1;
      while (left <= right){
          mid = left + (right - left) / 2;
          if (nums[maxIndex][mid] == target){
              return true;
          }
          else if (nums[maxIndex][mid] < target){
              left = mid + 1;
          }
          else {
              right = mid - 1;
          }
      }

      return false;
 }