# 0074. 搜索二维矩阵
###### tags: `Leetcode` `Medium` `脑筋急转弯` `二分查找`
Link: https://leetcode-cn.com/problems/search-a-2d-matrix/
## 思路
### 方法一

## Code
### 方法一

## Result

## Code in Java
### 方法一
从左下角或者右上角开始遍历

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        boolean exist = false;
        int m = matrix.length;
        int n = matrix[0].length;
        int row = m - 1, col = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] == target) {
                exist = true;
                break;
            } else if (matrix[row][col] > target) {
                row--;
            } else {
                col++;
            }
        }
        return exist;
    }
}

时间复杂度$O(m+n)$
空间复杂度$O(1)$
### 方法二：二分查找
虽然上边的方法已经不错了，但是并没有用到每一行的最后一个元素小于下一行的第一个元素这个特征。

思考：由于这个特征的存在，整个矩阵每一行从上到下首尾相接就是一个升序的一维数组。可以使用二分查找

#### 二分查找 I
两次二分查找：第一次找出第一列中最后一个不小于```target```的行，然后对此行再进行二分查找。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}

#### 二分查找 II
一次二分查找

class Solution {
    public boolean searchMatrix(int[][] mat, int t) {
        int m = mat.length, n = mat[0].length;
        int l = 0, r = m * n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mat[mid / n][mid % n] <= t) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return mat[r / n][r % n] == t;
    }
}

时间复杂度$O({\rm log}(mn))$
空间复杂度$O(1)$