Search 2D Matrix

# Search 2D Matrix ## Difficulty Medium ## Tags `matrix`, `binary search`, `divide and conquer` ## Problem Statement Write an efficient algorithm that searches for a value `target` in an `m x n` integer matrix. This matrix has the following properties: 1. Integers in each row are sorted in ascending order from left to right. 2. Integers in each column are sorted in ascending order from top to bottom. Return `True` if `target` is found, `False` otherwise. ## Constraints - m == matrix.length - n == matrix[i].length - 1 ≤ m, n ≤ 300 - -10⁹ ≤ matrix[i][j] ≤ 10⁹ - -10⁹ ≤ target ≤ 10⁹ ## Signatures ### Python ```python def search_matrix(matrix: List[List[int]], target: int) -> bool: pass ``` ### Java ```java public class Solution { public boolean search_matrix(List<List<Integer>> matrix, int target) { return null; } } ``` ### Csharp ```csharp public class Solution { public bool search_matrix(IList<IList<int>> matrix, int target) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: bool search_matrix(vector<vector<int>> matrix, int target) { } }; ``` ### C ```c bool search_matrix(vector<int*> matrix, int target) { } ``` ### Ruby ```ruby def search_matrix(matrix, target) end ``` ### Perl ```perl sub search_matrix { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def search_matrix(matrix: List[List[Int]], target: Int): Boolean = { } } ``` ### Haskell ```haskell search_matrix :: ... -> ... search_matrix args = undefined ``` ### Clojure ```clojure (defn search_matrix [matrix target] ) ``` ### Scheme ```scheme (define (search_matrix matrix target) ) ``` ## Examples ### Example 1 **Input:** ``` matrix = [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] target = 5 ``` **Output:** ``` True ``` ### Example 2 **Input:** ``` matrix = [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] target = 20 ``` **Output:** ``` False ``` ## Hints 1. Start from a corner where you can make decisions. 2. Top-right corner: if current > target, move left; if current < target, move down. 3. Bottom-left corner: if current > target, move up; if current < target, move right. 4. This achieves O(m + n) time complexity.