74 Search a 2D Matrix

tags: Medium,Array,Binary Search

74. Search a 2D Matrix

題目描述

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

範例

Example 1:

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

Example 2:

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

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10⁴ <= matrix[i][j], target <= 10⁴

解答

C#

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length;
        int n = matrix[0].Length;

        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid =  left + (right - left) / 2;
            (int i, int j) = Math.DivRem(mid, n); 

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

JimAug 7, 2023

C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        return binarySearch(matrix, target, m, n);
    }

    bool binarySearch(vector<vector<int>>& matrix, int target, int m, int n) {
        int left = 0, right = m * n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int r = mid / n;
            int c = mid % n;
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return false;
    }
};

Jerry Wu7 August, 2023

Javascript

function searchMatrix(matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;

  let min = 0;
  let max = m * n - 1;

  while (max >= min) {
    const mid = (max + min) >> 1;
    const midVal = matrix[~~(mid / n)][mid % n];

    if (midVal === target) return true;

    if (midVal > target) {
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }

  return false;
}

MarsgoatAug 7, 2023

Reference

回到題目列表