---
# System prepended metadata

title: 'LeetCode #74 [Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)'
tags: [Binary Search, LeetCode, Medium]

---

###### tags: `LeetCode` `Binary Search` `Medium`
# LeetCode #74 [Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)
### (Medium)

編寫一個高效的算法來判斷 m x n 矩陣中，是否存在一個目標值。該矩陣具有如下特性：

每行中的整數從左到右按升序排列。
每行的第一個整數大於前一行的最後一個整數。

![](https://i.imgur.com/jEuOpA9.png)

---
除了把一維數組改成二維數組外, 沒有其他變化, 注意索引轉換即可。

---
```
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int l=0, m=matrix.size(), n=matrix[0].size();
        int r=m*n-1;
        while(l<r){
            int mid=l+(r-l)/2;
            int i=mid/n, j=mid%n;
            if(matrix[i][j]==target)return true;
            if(matrix[i][j]<target)l=mid+1;
            else r=mid;
        }
        if(matrix[l/n][l%n]==target)return true;
        return false;
    }
};
```