# 74. Search a 2D Matrix

You are given an `m x n` integer matrix `matrix` with the following two properties:

* Each row is sorted in non-decreasing order.
    
* The first integer of each row is greater than the last integer of the previous row.
    

Given an integer `target`, return `true` *if* `target` *is in* `matrix` *or* `false` *otherwise*.

You must write a solution in `O(log(m * n))` time complexity.

### Thoughts

* I think this should be as simple as performing a binary search on the last index of each row, and then binary searching within the correct row from there
    
    * This should cut down on the number of searches made and achieve O(log m\*n)
        
    * yea just two consecutive while loops seems to be the play here
        

### Solution

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowLow = 0, rowHigh = matrix.length - 1;
        int colLow = 0, colHigh = matrix[0].length - 1;
        int row = 0;

        // Binary search by the last element of the rows to find which row the target would be in
        while (rowLow <= rowHigh) {
            int rowMid = ((rowHigh - rowLow) / 2) + rowLow;
            if (matrix[rowMid][matrix[rowMid].length - 1] >= target) {
                if (matrix[rowMid][matrix[rowMid].length - 1] == target) {
                    return true;
                }
                row = rowMid;
            }

            if (matrix[rowMid][matrix[rowMid].length - 1] > target) {
                rowHigh = rowMid - 1;
            } else {
                rowLow = rowMid + 1;
            }
        }

        // Binary search within the rows to find (or not find) the target
        while (colLow <= colHigh) {
            int colMid = ((colHigh - colLow) / 2) + colLow;
            if (matrix[row][colMid] == target) {
                return true;
            }

            if (matrix[row][colMid] > target) {
                colHigh = colMid - 1;
            } else {
                colLow = colMid + 1;
            }
        } 

        return false;
    }
}
```

**Time Complexity:** O(log m \* n)  
**Space Complexity:** O(1)

### Conclusion

This one was much easier since I had just reviewed my binary search knowledge by doing [704\. Binary Search](https://lc.sweezy.io/704). This was much more fun and interesting than just a regular binary search problem. I felt like my brain was more stimulated by this than 704. Overall though, I definitely still need to brush up on my data structures and algorithms knowledge. I can feel some of my knowledge there slipping away and I really would like to prevent that from happening.