LeetCode 74. Search a 2D Matrix

Problem

LeetCode 74. Search a 2D Matrix

1. 题目简述

写出一个函数来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

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

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

2. 算法思路

Binary Search

这道题的矩阵其实是一个完全有序的矩阵，有两种做法：第一种是先找行数，在找列数；第二种做法是只做一次二分查找，l = 0，r = m * n - 1，然后通过算式来计算middle的横纵坐标来进行下一步计算。

3. 解法

1.分别计算横纵坐标：需要注意的是第一次查找完以后，如果发现这个数比全局最小都小，也就是l = 0，则直接返回-1.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 两次二分，先确定行，再确定列
        
        int m = matrix.length, n = matrix[0].length, row = 0, col = 0;
        
        if (matrix[0][0] > target || matrix[m - 1][n - 1] < target) {
            return false;
        }
        
        // 确定行，这里是要找右边界，也就是小于等于target的最大的那个队首。
        int l = 0, r = m - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (matrix[mid][0] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        
        row = l;
        
        // 确定列，这里是找出最准确的那个数，左右边界无所谓
        l = 0;
        r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return matrix[row][l] == target;
        
    }
}

2. 一次计算二分搜索

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

    // binary search
    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;
  }
}