# Quadruple Search with N^(log base4 of 3)

• 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);
}
}
};

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