> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/binary_search_lei/matrix_binary_search.md).

# Matrix Binary Search

## [Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)

考点只有一个：2D array 降维成 1D array 的 index trick.

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

        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;

            if(matrix[row][col] == target){
                return true;
            } else if(matrix[row][col] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}
```

## [Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/)

实现的时候稍微纠结了一下收边的问题，后来一想，如果到了边上还走到越界的位置上，已经说明没有合理解了，跳出循环返回 false 就行。

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

        int rows = matrix.length;
        int cols = matrix[0].length;

        int x = rows - 1;
        int y = 0;

        while(x >= 0 && y < cols){
            int cur = matrix[x][y];
            if(cur == target){
                return true;
            } else if(cur < target){
                y ++;
            } else {
                x --;
            }
        }

        return false;
    }
}
```