# 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)$

- 程式碼

    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>