Intuition
- The tricky part to understand here is the idea of mid // n as row and mid % n as column when picking the element to compare against target.
- You can consider the entire matrix as a sorted array of length m x n
- When you use
//, you’re determining how many “complete rows” you’ve gone through. - When you use
%, you’re figuring out the “leftover” position within the current row.
Runtime
to search through the rows and columns via a binary search.
Code
Math Solution
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
l, h = 0, m * n - 1
while l <= h:
mid = (l + h) // 2
elem = matrix[mid // n][mid % n]
if target == elem:
return True
elif target < elem:
h = mid - 1
else:
l = mid + 1
return FalseBinary Search also on Columns to Prevent Linear Scan of Last Column
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
def binarySearchRow(r, l, h):
while l <= h:
mid = (l + h) // 2
elem = matrix[r][mid]
if target == elem:
return True
elif target < elem:
h = mid - 1
else:
l = mid + 1
def binarySearchCol(l, h):
while l <= h:
mid = (l + h) // 2
elem = matrix[mid][-1]
if target == elem:
return True
elif target < elem:
if target >= matrix[mid][0]:
return binarySearchRow(mid, 0, n - 1)
h = mid - 1
else:
l = mid + 1
return False
return binarySearchCol(0, m - 1)Binary Search with Linear Scan of Last Column
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
def binarySearch(r, l, h):
while l <= h:
mid = (l + h) // 2
elem = matrix[r][mid]
if target == elem:
return True
elif target < elem:
h = mid - 1
else:
l = mid + 1
m, n = len(matrix), len(matrix[0])
for r in range(m):
if matrix[r][0] <= target <= matrix[r][-1]:
return binarySearch(r, 0, n - 1)
return False