You are given an m x n integer matrix where each row is sorted left to right, and the first value of every row is greater than the last value of the row above it. Return true if target is in the matrix. The solution must be O(log(m * n)).
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking every cell is O(m * n). Binary searching each row is O(m log n). But because each row starts above where the previous row ended, laying the rows end to end gives one sorted array of length m * n. We never build it: index k of that virtual array lives at matrix[k / n][k % n]. A single binary search over k then takes O(log(m * n)).
Algorithm
- Let
m= number of rows,n= number of columns. Setlo = 0,hi = m * n - 1. - While
lo <= hi, computemidand readv = matrix[mid / n][mid % n]. - If
v == target, return true. - If
v < target, setlo = mid + 1, elsehi = mid - 1. - Return false when the loop ends.
O(log(m * n))Space: O(1)class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) lo, hi = 0, m * n - 1 # treat the matrix as one sorted array while lo <= hi: mid = (lo + hi) // 2 v = matrix[mid // n][mid % n] # index -> (row, col) if v == target: return True if v < target: lo = mid + 1 else: hi = mid - 1 return False