# O(mlgn) iterative C++(12ms) and recursive C#(184ms)

• C++ iterative version

``````// iterative O(mlgn) solution
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if(m == 0)
return false;
int n = matrix[0].size();
if(n == 0)
return false;

// Binary search each row
for(int i = 0; i < m; ++i)
{
vector<int>& row = matrix[i];
int j = 0;
int min = 0; int max = n-1;
// iterative process
while(max - min >= 0)
{
j = (max+min)/2;
int value = row[j];
if(value == target)
return true;
else if(value < target)
// search right value
min = j+1;
else
// search left values
max = j-1;
}
}
return false;
}
``````

C# recursive version

``````// Recursive O(mlgn) solution
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;

// Binary search each row
for(int i = 0; i < m; ++i)
{
if(BinarySearch(matrix, target, i, 0, n-1))
return true;
}
return false;
}

bool BinarySearch(int[,] matrix, int target, int i, int min, int max)
{
if(min > max)
return false;
int j = (max+min)/2;
int value = matrix[i,j];
if(value == target)
return true;
else if(value < target)
// search right value
return BinarySearch(matrix, target, i, j+1, max);
else
// search left values
return BinarySearch(matrix, target, i, min, j-1);
}``````

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