leetcode : Search a 2D Matrix

runtime 0 ms, beats 100% of cpp submissions
O(log(mn)) solution with explanation

tags: binary search

🔗 link

Search a 2D Matrix

📖 description

給定一個被排序過的 2 維陣列，找到目標元素。

ex.
    Input: 
        matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

    Output: true

🧠 solution

本題就是一個 binary search 的變形，與一般方法不同的只有在搜尋時需要將索引值轉換成兩個引數。

⏳ time complexity

共有 mn 個元素， binary search 的時間複雜度為 O(log(mn))
總時間複雜度 O(log(mn))

📝 code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& mat, int t) {
        int m = mat.size();
        int n = mat[0].size();
        int siz = m*n;
        int l = 0,r = siz-1;
        while(r>=l){
            int mid = (r+l)/2;
            if(mat[mid/n][mid%n] == t){ // 轉換成兩個座標
                return true;
            }
            else if(mat[mid/n][mid%n] < t){
                l = mid+1;
            }
            else{
                r = mid-1;
            }
        }
        return false;
    }
};