Description:
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.
Examples:
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
Solution in Python:
Python
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# Get the number of rows (m) and columns (n)
m = len(matrix)
n = len(matrix[0])
# Initialize left and right pointers for binary search
left = 0
right = m * n - 1
while left <= right:
# Calculate the middle index
mid = (left + right) // 2
# Convert the middle index to row and column indices in the 2D matrix
mid_value = matrix[mid // n][mid % n]
if mid_value == target:
# If the middle value is the target, return True
return True
elif mid_value < target:
# If the middle value is less than the target, move the left pointer to the right of mid
left = mid + 1
else:
# If the middle value is greater than the target, move the right pointer to the left of mid
right = mid - 1
# If the target is not found, return False
return FalseDetailed Comments:
- Matrix Dimensions:
m = len(matrix): Number of rows in the matrix.n = len(matrix[0]): Number of columns in the matrix.
- Binary Search Initialization:
left = 0: The starting index of the binary search, corresponding to the first element of the matrix.right = m * n - 1: The ending index of the binary search, corresponding to the last element of the matrix.
- Binary Search Loop:
- The loop continues as long as
left <= right, ensuring we still have elements to consider.
- The loop continues as long as
- Calculate Middle Index:
mid = (left + right) // 2: Compute the middle index.
- Convert Middle Index to Matrix Indices:
mid_value = matrix[mid // n][mid % n]: Convert the 1Dmidindex to 2D row and column indices:mid // ngives the row index.mid % ngives the column index.
- Comparison and Adjustment of Pointers:
- If
mid_value == target, the target is found, so returnTrue. - If
mid_value < target, adjust theleftpointer to search the right half (left = mid + 1). - If
mid_value > target, adjust therightpointer to search the left half (right = mid - 1).
- If
- Return False:
- If the loop completes without finding the target, return
False.
- If the loop completes without finding the target, return
This approach leverages binary search on a conceptual 1D array representation of the 2D matrix, maintaining the required O(log(m * n)) time complexity.
Solution in Javascript:
JavaScript
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
// Get the number of rows (m) and columns (n)
const m = matrix.length;
const n = matrix[0].length;
// Initialize left and right pointers for binary search
let left = 0;
let right = m * n - 1;
while (left <= right) {
// Calculate the middle index
const mid = Math.floor((left + right) / 2);
// Convert the middle index to row and column indices in the 2D matrix
const midValue = matrix[Math.floor(mid / n)][mid % n];
if (midValue === target) {
// If the middle value is the target, return true
return true;
} else if (midValue < target) {
// If the middle value is less than the target, move the left pointer to the right of mid
left = mid + 1;
} else {
// If the middle value is greater than the target, move the right pointer to the left of mid
right = mid - 1;
}
}
// If the target is not found, return false
return false;
};Solution in Java:
Java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// Get the number of rows (m) and columns (n)
int m = matrix.length;
int n = matrix[0].length;
// Initialize left and right pointers for binary search
int left = 0;
int right = m * n - 1;
while (left <= right) {
// Calculate the middle index
int mid = (left + right) / 2;
// Convert the middle index to row and column indices in the 2D matrix
int midValue = matrix[mid / n][mid % n];
if (midValue == target) {
// If the middle value is the target, return true
return true;
} else if (midValue < target) {
// If the middle value is less than the target, move the left pointer to the right of mid
left = mid + 1;
} else {
// If the middle value is greater than the target, move the right pointer to the left of mid
right = mid - 1;
}
}
// If the target is not found, return false
return false;
}
}Solution in C#:
C#
public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
// Get the number of rows (m) and columns (n)
int m = matrix.Length;
int n = matrix[0].Length;
// Initialize left and right pointers for binary search
int left = 0;
int right = m * n - 1;
while (left <= right) {
// Calculate the middle index
int mid = (left + right) / 2;
// Convert the middle index to row and column indices in the 2D matrix
int midValue = matrix[mid / n][mid % n];
if (midValue == target) {
// If the middle value is the target, return true
return true;
} else if (midValue < target) {
// If the middle value is less than the target, move the left pointer to the right of mid
left = mid + 1;
} else {
// If the middle value is greater than the target, move the right pointer to the left of mid
right = mid - 1;
}
}
// If the target is not found, return false
return false;
}
}