How do you search a sorted 2D matrix?

Question presented to candidate: "You are given a matrix of integers that is sorted, and a target. Return whether the target is in the matrix. Please write it in Python, and tell me how your approach depends on how exactly the matrix is sorted."

What a strong answer should cover:

• Asks which shape: rows chaining into one sorted sequence (LeetCode 74) or rows and columns sorted independently (LeetCode 240).
• Shape 1: binary search over 0 .. m*n - 1 with index mapping divmod(mid, cols), O(log(m n)) time, O(1) space.
• Shape 2: staircase walk from the top-right corner, dropping a row or column per step, O(m + n), with the reason the top-left corner does not work.
• Brute force O(m n) and row-by-row bisect O(m log n) as baselines.
• Python specifics: divmod, guarding matrix[0] on an empty list (IndexError), // not /, and the [[0] * n] * m aliasing trap when building test matrices.

Clarifying questions expected:

• "Does each row start after the previous row ends, or are rows and columns sorted separately?"
• "Return a boolean or the position?"
• "Can the matrix or its rows be empty?"

Code / implementation expected: Yes — search_matrix(matrix, target) for Shape 1 and a staircase function for Shape 2, in Python.