# 74&240. Search a 2D Matrix I & II

**Search a 2D Matrix I**

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.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/05/mat.jpg)

<pre><code><strong>Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
</strong><strong>Output: true
</strong></code></pre>

***My Solutions:***

因为所有数字都是递增的，可以用二分法。用数字的个数来定位数字在哪个格子。

```
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int row = matrix.length, col = matrix[0].length;
        int begin = 0, end = row * col - 1;
        
        if (target < matrix[0][0] || target > matrix[row - 1][col - 1]) return false;
        
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            int midValue = matrix[mid / col][mid % col];
            
            if (midValue == target) return true;
            else if (midValue < target) begin = mid;
            else end = mid;
        }
        if (matrix[begin / col][begin % col] == target) return true;
        if (matrix[end / col][end % col] == target) return true;
        return false;
    }
}
```

**Search a 2D Matrix II**

Write an efficient algorithm that searches for a value `target` in an `m x n` integer matrix `matrix`. This matrix has the following properties:

* Integers in each row are sorted in ascending from left to right.
* Integers in each column are sorted in ascending from top to bottom.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/24/searchgrid2.jpg)

<pre><code><strong>Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
</strong><strong>Output: true
</strong></code></pre>

***My Solutions:***

从matrix的右上角或者左下角找起，如果右上角的数字比target小，说明要移动行数，往下一行找。如果右上角的数字比target大，说明要移动列数，往左边一列找。

```
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int row = 0, col = matrix[0].length - 1;
    
    while (col >= 0 && row <= matrix.length - 1) {
        
        // can use rightTop or leftBottom
        int rightTop = matrix[row][col];
        if (rightTop == target) return true;
        if (rightTop < target) row++;
        else col--;
    }
    return false;
}
```
