---

1. Problem Summary

You are given a 2D matrix with the following properties:

1. Each row is sorted in ascending order
2. The first element of each row is greater than the last element of the previous row

Your task is to determine whether a given integer target exists in the matrix.
Return:

• true if target is found
• false otherwise

Important details:

• The matrix behaves like a sorted 1D array when flattened
• No need to modify the matrix
• Must search efficiently (better than row-by-row scan)

Example interpretation:
If the matrix is:

[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]

and target = 3 → return true
and target = 13 → return false

---

2. Key Insights

Matrix behaves like a sorted linear array

Because:

• Rows are sorted
• Next row always starts with a larger number
• Therefore, the matrix can be treated as one increasing sequence

Binary search can be applied

Instead of searching row-wise or column-wise, we map 1D indices to 2D positions.

Index conversion formula

For a matrix with dimensions:

rows = m
cols = n

Mapping:

midIndex → row = midIndex / n
midIndex → col = midIndex % n

Time must be O(log(m*n))

Binary search meets this requirement.

---

3. Approach

Binary Search on Flattened Matrix

Steps:

1. Compute total elements: m * n
2. Set: left = 0 right = m*n - 1
3. While left ≤ right:
   • compute mid index
   • convert mid to matrix[row][col]
   • compare with target
   • adjust search boundaries
4. If found → return true
5. If loop ends → return false

No need to physically flatten the matrix.

---

4. Time and Space Complexity

Time Complexity: O(log(m*n))

Binary search over all elements.

Space Complexity: O(1)

No additional storage required.

---

5. Java Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        int left = 0;
        int right = rows * cols - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            int row = mid / cols;
            int col = mid % cols;

            int value = matrix[row][col];

            if (value == target) {
                return true;
            } else if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

---

6. Dry Run Examples

Example 1

Input:

matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]
target = 3

Total elements = 12
left=0, right=11

mid = 5
row = 5/4 = 1
col = 5%4 = 1
value = 11 → greater than target → move right = 4

mid = 2
row = 2/4 = 0
col = 2%4 = 0
value = 5 → greater than target → move right = 1

mid = 0
row = 0
col = 0
value = 1 → less than target → left = 1

mid = 1
row = 0
col = 1
value = 3 → equals target

Output:

true

---

Example 2

Input:

matrix = [
  [1, 3, 5],
  [7, 9, 11]
]
target = 8

Binary search evaluates values in order, never finds 8 → return false

Output:

false

---

Example 3 (single row)

matrix = [[2, 4, 6, 8]]
target = 6

Binary search within row works → return true

---

Example 4 (single element)

matrix = [[5]]
target = 5 → true  
target = 2 → false

---

7. Why This Solution Works

• Uses matrix ordering guarantees
• Avoids searching row-by-row (O(m + n))
• Avoids scanning all elements (O(m*n))
• Binary search ensures logarithmic performance
• Mapping logic ensures constant-space execution
• Handles all matrix dimensions safely

---

8. Common Mistakes

1. Using 2D binary search on rows then columns (slower)
2. Forgetting integer division rules
3. Using (left+right)/2 without overflow-safe formula
4. Assuming rows may be empty
5. Not handling 1-row or 1-column matrices correctly