# C++/C# divide and conquer solution

• C++ version

``````bool searchMatrix(vector<vector<int>>& matrix, int target) {
// check bad input
int m = matrix.size();
if(m == 0)
return false;
int n = matrix[0].size();
if(n == 0)
return false;
return binarySearch(matrix, target, 0, m-1, 0, n-1);
}

bool binarySearch(vector<vector<int>>& matrix, int target,
int min_i, int max_i,
int min_j, int max_j){
if(min_i > max_i)
return false;
if(min_j > max_j)
return false;
int i = (min_i + max_i)/2;
int j = (min_j + max_j)/2;

int value = matrix[i][j];
if(value == target)
return true;
else if(value < target)
{
return binarySearch(matrix, target, min_i, max_i, j+1, max_j)
|| binarySearch(matrix, target, i+1, max_i, min_j, j);
}
else
{
return binarySearch(matrix, target, min_i, max_i, min_j, j-1)
|| binarySearch(matrix, target, min_i, i-1, j, max_j);
}
}
``````

C# version

``````public bool SearchMatrix(int[,] matrix, int target) {
if(matrix == null)
return false;
int m = matrix.GetLength(0);
int n = matrix.GetLength(1);
if(n == 0 && m == 0)
return false;
return BinarySearch(matrix, target, 0, m-1, 0, n-1);
}

bool BinarySearch(int[,] matrix, int target,
int min_i, int max_i,
int min_j, int max_j){
if(min_i > max_i)
return false;
if(min_j > max_j)
return false;
int i = (min_i + max_i)/2;
int j = (min_j + max_j)/2;

int value = matrix[i,j];
if(value == target)
return true;
else if(value < target)
{
return BinarySearch(matrix, target, min_i, max_i, j+1, max_j)
|| BinarySearch(matrix, target, i+1, max_i, min_j, j);
}
else
{
return BinarySearch(matrix, target, min_i, max_i, min_j, j-1)
|| BinarySearch(matrix, target, min_i, i-1, j, max_j);
}
}``````

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