We’re given a 2D matrix and asked to determine if a specific number exists or not. We use binary search in 2 dimensions to accomplish this. Instead of setting the right pointer to the size of one array, we set the right pointer to m * n - 1 where m is the length of the rows and n is the length of the columns.
We calculate the middle selection like always, (r + l) // 2, however, when we index into the 2D matrix, we have to account for it’s 2D nature. Thus, for rows we index into matrix[mid // n] and for columns we index into matrix[mid % n].
With these changes, we conduct our standard binary search and return the result.
The solution is as follows:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
l, r = 0, m * n - 1
while l <= r:
mid = (r + l) // 2
num = matrix[mid // n][mid % n]
if num == target:
return True
if num > target:
r = mid - 1
else:
l = mid + 1
return False_ Time Complexity:
O(log(mn)) - Standard binary search time complexity.
_ Space Complexity:
O(1) - Binary search uses constant space.