Leetcode: Binary Search Matrix
The solution is a normal binary search as it would be done on a single array. The difference
is that it is a two-dimensional array. To solve for this, we treat the array as a one-dimensional
array and check the middle element by calculating the row and column.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
left = 0
right = len(matrix) * len(matrix[0])
return self.inner(matrix, target, left, right)
def inner(self, matrix, target, left, right) -> bool:
middle = (left+right)//2
row = middle//len(matrix[0])
col = middle - (row*len(matrix[0]))
if matrix[row][col] == target:
return True
if right - 1 > left:
if matrix[row][col] < target:
return self.inner(matrix, target, middle, right)
else:
return self.inner(matrix, target, left, middle)
else:
return False