---
# System prepended metadata

title: LeetCode 74. Search a 2D Matrix

---

# LeetCode 74. Search a 2D Matrix
[LeetCode 74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/) (難度 通過率)
<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>m == matrix.length</code></li>
    <li><code>n == matrix[i].length</code></li>
    <li><code>1 <= m, n <= 100</code></li>
    <li><code>-10^4 <= matrix[i][j], target <= 10^4</code></li>
    </ul>

- Solution
    這題要問 target 有沒有存在 matrix 中。
    依照題目所敘，他是一個不遞減的 matrix ，所以可以很輕鬆地使用 binary search tree 去找。

    - 時間複雜度: $O(log(n))$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int left = 0, right = matrix.size() * matrix[0].size() - 1;
            int idx[2] = {};
            int center = (right - left) / 2 + left;
            while (left <= right) {
                center = (right - left) / 2 + left;
                idx[0] = center / matrix[0].size();
                idx[1] = center % matrix[0].size();
                cout << center << ' ' << idx[0] << ' ' << idx[1] << ' ' << matrix[idx[0]][idx[1]] << endl;
                if (matrix[idx[0]][idx[1]] == target)     return true;
                else if (matrix[idx[0]][idx[1]] < target) left = center + 1;
                else if (matrix[idx[0]][idx[1]] > target) right = center - 1;
            }
            return false;
        }
    };
    ```
</details>