Quadruple Search with N^(log base4 of 3)


  • 0
    S

    By doing comparison, every time you can eliminate 1/4 of the elements.
    then T(N) = 3T(N/4). By mater method, the complexity is N^(log4(3)) where N = m * n

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m = matrix.size();
            if (m == 0) return false;
            int n = matrix[0].size();
            return __searchMatrix(matrix, target, 0, 0, m-1, n-1);
        }
    
        bool __searchMatrix(vector<vector<int>>& matrix, int target, int rowLo, int colLo, int rowHi, int colHi) {
            if (rowLo > rowHi || colLo > colHi) return false;
            if (target < matrix[rowLo][colLo] || target > matrix[rowHi][colHi]) return false;
        
            int rowMid = rowLo + (rowHi - rowLo) / 2;
            int colMid = colLo + (colHi - colLo) / 2;
        
            int comp = matrix[rowMid][colMid];
            if (target == comp) {
                return true;
            } else if (target < comp) {
                return __searchMatrix(matrix, target, rowLo, colLo, rowMid - 1, colHi) ||
                        __searchMatrix(matrix, target, rowMid, colLo, rowHi, colMid - 1);
            } else {
                return __searchMatrix(matrix, target, rowMid + 1, colLo, rowHi, colHi) ||
                        __searchMatrix(matrix, target, rowLo, colMid + 1, rowMid, colHi);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.