# 3 different Binary Search Solutions and 1 O(M+N)

• [1] Quad Search Solution: the idea is to get the middle index and split the matrix to 4 parts, divide and conquer.

``````public bool SearchMatrix(int[,] matrix, int target) {
return quadSearch(matrix, 0, 0, matrix.GetLength(0) - 1, matrix.GetLength(1) - 1, target);
}
private bool quadSearch(int[,] matrix, int x1, int y1, int x2, int y2, int target)
{
if(x1 >= matrix.GetLength(0) || y1 >= matrix.GetLength(1) || target > matrix[x2, y2] || target < matrix[x1, y1])
return false;
if(x1 == x2 && y1 == y2)
if(matrix[x1, y1] == target) return true;
else return false;
int midX = (x1 + x2) >> 1, midY = (y1 + y2) >>1;
if(matrix[midX, midY] == target) return true;
else if(matrix[midX, midY] > target)
return quadSearch(matrix,       x1,       y1, midX, midY, target) ||
quadSearch(matrix, midX + 1,       y1,   x2, midY, target) ||
quadSearch(matrix,       x1, midY + 1, midX,   y2, target);
else
return quadSearch(matrix, midX + 1,       y1,   x2, midY, target) ||
quadSearch(matrix,       x1, midY + 1, midX,   y2, target) ||
quadSearch(matrix, midX + 1, midY + 1,   x2,   y2, target);
}
``````

[2] O(Log(M)+Log(N)) Iterative Solution: the idea is to b-search the up/down/left/right boundaries and do the b-search in each smaller matrix repeatedly. The worst case is O(M+N). 408ms

``````public bool SearchMatrix(int[,] matrix, int target) {
int m = matrix.GetLength(0), n = matrix.GetLength(1);
int x1 = 0, y1 = 0, x2 = m - 1, y2 = n - 1;
while (m != 1 || n != 1)
{
//1) B-Search to Get Up and Down boundaries
int iUp = x1, iDown = x2, iUpBoundary, iDownBoundary;
while (iUp <= iDown){
int mid = (iUp + iDown) >> 1;
if (matrix[mid, y2] > target) iDown = mid - 1;
else if (matrix[mid, y2] < target) iUp = mid + 1;
else if (matrix[mid, y2] == target) return true;
}
if (n == 1) return false;
iUpBoundary = iUp; iUp = x1; iDown = x2;
while (iUp <= iDown){
int mid = (iUp + iDown) >> 1;
if (matrix[mid, y1] > target) iDown = mid - 1;
else if (matrix[mid, y1] < target) iUp = mid + 1;
else if (matrix[mid, y1] == target) return true;
}
if (iUpBoundary > (iDownBoundary = iDown)) return false;
//2) B-Search to Get Left and Right boundaries
int iLeft = y1, iRight = y2, iLeftBoundary, iRightBoundary;
while (iLeft <= iRight){
int mid = (iLeft + iRight) >> 1;
if (matrix[iDownBoundary, mid] > target) iRight = mid - 1;
else if (matrix[iDownBoundary, mid] < target) iLeft = mid + 1;
else if (matrix[iDownBoundary, mid] == target) return true;
}
if (m == 1) return false;
iLeftBoundary = iLeft; iLeft = y1; iRight = y2;
while (iLeft <= iRight){
int mid = (iLeft + iRight) >> 1;
if (matrix[iUpBoundary, mid] > target) iRight = mid - 1;
else if (matrix[iUpBoundary, mid] < target) iLeft = mid + 1;
else if (matrix[iUpBoundary, mid] == target) return true;
}
if (iLeftBoundary > (iRightBoundary = iRight)) return false;
x1 = iUpBoundary; y1 = iLeftBoundary;
x2 = iDownBoundary; y2 = iRightBoundary;
m = x2 - x1 + 1; n = y2 - y1 + 1;
}
return (m == 1 && n == 1 && matrix[x1, y1] == target) ? true : false;
}
``````

[3] O(M*LogN) Solution: First, b-search row upper boundary, then b-search row down boundary, finally b-search each rows in the range of boundaries.

``````public bool SearchMatrix(int[,] matrix, int target) {
int m = matrix.GetLength(0), n = matrix.GetLength(1), iUp = 0, iDown = m - 1, iDownBoundary, iUpBoundary;
while(iUp < iDown){
int mid = (iUp + iDown) >> 1;
if(matrix[mid, n - 1] > target) iDown = mid;
else if(matrix[mid, n - 1] < target) iUp = mid + 1;
else if(matrix[mid, n - 1] == target) return true;
}
iDownBoundary = iDown; iUp = 0; iDown = m - 1;
while(iUp <= iDown){
int mid = (iUp + iDown) >> 1;
if(matrix[mid, 0] > target) iDown = mid - 1;
else if(matrix[mid, 0] < target) iUp = mid + 1;
else if(matrix[mid, 0] == target) return true;
}
iUpBoundary = iDown; //  iDownBoundary <= iUpboundary
for(int i = iDownBoundary; i <= iUpBoundary; i++){
int iLeft = 0, iRight = n - 1;
while(iLeft <= iRight){
int mid = (iLeft + iRight) >> 1;
if(matrix[i, mid] > target) iRight = mid - 1;
else if(matrix[i, mid] < target) iLeft = mid + 1;
else if(matrix[i, mid] == target) return true;
}
}
return false;
}
``````

[4] O(M+N) 412ms

``````public bool SearchMatrix(int[,] matrix, int target) {
for(int i = matrix.GetLength(0) - 1, j = 0; i >= 0 && j < matrix.GetLength(1);)
if(matrix[i, j] > target) i--;
else if (matrix[i, j] < target) j++;
else return true;
return false;
}``````

• hi
what is the time complexity of your first Quad Search Solution ?

Thanks

• Scott, it's
T(n, = 3 [ 3T(n ] + c = 3 [ 3 [ 3T(n/8) + c ] + c ] + c = 3kk(3k - 1)/2 = 3k k) = 3lg n(3lg nlg 3) <== 3lg nlg 3 = O(n1.58)

• @scott I think it is O(3^log4(MN)). T(MN) = 3T(1/4 * MN) + O(1)

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