Search a 2D Matrix
- 2 min read
- LC-Medium
- Binary-search
3 years ago
Solution
- Just do a binary search 2 times.
- We basically compare the target with the last value and the first value in a row:
- If it is lesser than the first value in a row, then it possibly exists in a row above
- If it is greater than the last value in a row, then it possibly exists in a row below
- If none of these conditions are met, either it is in the current row we're looking at or not in the matrix at all.
- The
ifcondition in the middle is for the case where the target was not present in the entire matrix. This only happens when you forcefully break out of the while loop, in which case the conditiontop <= bottomwould evaluate to True. We only continue to the next binary search if this is NOT the case.
| Time | Space | Explanation | |
|---|---|---|---|
O(log m + log n) | O(1) |
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
nrows, ncols = len(matrix), len(matrix[0])
top, bottom = 0, nrows - 1
while top <= bottom:
row = (top + bottom) // 2
if target > matrix[row][-1]:
top = row + 1
elif target < matrix[row][0]:
bottom = row - 1
else:
break
if not (top <= bottom):
return False
left, right = 0, ncols - 1
while left <= right:
col = (left + right) // 2
if target > matrix[row][col]:
left = col + 1
elif target < matrix[row][col]:
right = col - 1
else:
return True
return False