# LeetCode: Search a 2D Matrix C#

https://leetcode.com/problems/search-a-2d-matrix/

Write an efficient algorithm that searches for a value in an m x n
matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer
of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:

Input:
matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false


Please review for performance. maybe there are better solutions but this is how my brain worked on this question.

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
/// <summary>
/// https://leetcode.com/problems/search-a-2d-matrix/
/// </summary>
[TestClass]
public class SearchA2DMatrixTest
{
[TestMethod]
public void ExampleTest()
{
int[][] matrix =
{
new[] {1, 3, 5, 7},
new[] {10, 11, 16, 20},
new[] {23, 30, 34, 50}
};
int target = 3;
Assert.IsTrue(SearchMatrix(matrix, target));
}

[TestMethod]
public void FailedTest()
{
int[][] matrix =
{
new[] {1},
new[] {3},
};
int target = 3;
Assert.IsTrue(SearchMatrix(matrix, target));
}

[TestMethod]
public void FailedTest2()
{
int[][] matrix =
{
new[] {1,3,5,6},
new[] {10,11,16,20},
new[] {23,30,34,50},
};
int target = 11;
Assert.IsTrue(SearchMatrix(matrix, target));
}
public bool SearchMatrix(int[][] matrix, int target)
{
if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0)
{
return false;
}
if (target < matrix[0][0] || target > matrix[matrix.Length - 1][matrix[0].Length - 1])
{
return false;
}
int top = matrix.Length - 1;
int bottom =0;
int mid = 0;
while (bottom <= top)
{
mid = ((top - bottom) / 2) + bottom;
if (matrix[mid][0] == target)
{
return true;
}
if (matrix[mid][0] > target)
{
top = mid - 1;
}
else
{
bottom = mid + 1;
}
}

//if the first cell of the curr row(mid)
// is bigger than the target,
// the target is in the previous row
if (matrix[mid][0] > target)
{
mid--;
}

int left = 0;
int right = matrix[0].Length - 1;
int cm;
while (left <= right)
{
cm = ((right - left) / 2) + left;
if (matrix[mid][cm] == target)
{
return true;
}
if (matrix[mid][cm] > target)
{
right = cm - 1;
}
else
{
left = cm + 1;
}
}
return false;
}
}
}