> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/search_a_2d_matrix.md).

# Search a 2D Matrix

<https://leetcode.com/problems/search-a-2d-matrix/description/>

> Write an efficient algorithm that searches for a value in an m x n matrix.
>
> This matrix has the following properties:
>
> Integers in each row are sorted from left to right.\
> The first integer of each row is greater than the last integer of the previous row.

## Thoughts

把问题依然当成是一维的bin search, 直到必须读取matrix数据时才把一维index转化成二维坐标。

## Code

```
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = m == 0 ? 0 : matrix[0].length;
        int start = 0, end = m * n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid / n][mid % n] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        if (n == 0 || start == m * n || matrix[start / n][start % n] != target) {
            return false;
        } else {
            return true;
        }
    }
}
```

## Analysis

O(lgmn)时间复杂度，O(1)空间复杂度。

在调用维度转换时误把n写成了m.