1
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.