LeetCode 74 · Binary Search · concept: modified-binary-search
Problem
An m × n matrix where each row is sorted and the first value of each row exceeds the last of the previous row. Return whether target is present. O(log(m·n)) required.
[[1, 3, 5, 7],
[10,11,16,20],
[23,30,34,60]], target = 3 -> true
The idea — one sorted array in disguise
The constraints mean the matrix, read row by row, is a single sorted sequence of m·n elements. So binary search over the virtual index 0 … m·n − 1 and map it back to 2D coordinates: row = idx // n, col = idx % n.
def searchMatrix(matrix, target):
m, n = len(matrix), len(matrix[0])
l, r = 0, m * n - 1
while l <= r:
mid = l + (r - l) // 2
val = matrix[mid // n][mid % n] # map flat index -> (row, col)
if val == target:
return True
elif val < target:
l = mid + 1
else:
r = mid - 1
return FalseTime O(log(m·n)), space O(1).
The index mapping
divmod(mid, n) converts a flat index to (row, col): integer-divide by the row width for the row, take the remainder for the column. This is the inverse of the row-major layout arrays use in memory (arrays) — the same trick behind treating any 2D grid as 1D.
Alternative — two binary searches / staircase
Binary search the column of first-elements to find the candidate row, then binary search within it (also O(log m + log n)). A different matrix (“row- and column-sorted”, LC 240) instead uses a staircase walk from the top-right in O(m + n).
Key insight
A fully-sorted matrix is a 1D sorted array with a coordinate transform. Recognizing the flattening lets you reuse plain binary search; the only new idea is the divmod index mapping.
Related
- concept: modified-binary-search; layout in arrays
- prev: Binary Search · next: Koko Eating Bananas
Software engineering
Infrastructure & security
Computer science
Hardware & engineering