Question
Formatted question description: https://leetcode.ca/all/240.html
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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following 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]
]
Given target = 5, return true.
Given target = 20, return false.
@tagbinarysearch
Algorithm
It is an extension of the previous 74. Search a 2D Matrix
.
74. Search a 2D Matrix
is that the first number of each line is greater than the last number of the previous line. So for that question, you can expand the twodimensional array into a onebit array with a twocheck search.
And this question has two unique numbers, the lower left
corner and the upper right
corner. The 18
in the lower left corner of above example, all the numbers going up become smaller, and all the numbers going to the right increase, then we can compare with the target number,
 If the number of targets is large, search to the right,
 If the target number is small, search upwards.
In this way, it can be judged whether the target number exists. Of course, we can also put the starting number in the upper right corner, search left and down, and set the stop condition correctly.
valid in Search_a_2D_Matrix, but not in II
{1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
Please refer to this comment, which is awesome https://leetcode.com/problems/searcha2dmatrixii/discuss/66140/MyconciseO(m+n)Javasolution/68155 .
Code
Java

public class Search_a_2D_Matrix_II { public static void main(String[] args) { Search_a_2D_Matrix_II out = new Search_a_2D_Matrix_II(); Solution s = out.new Solution(); System.out.println(s.searchMatrix( new int[][]{ {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} }, 5 )); } /* valid in Search_a_2D_Matrix, but not in II {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, */ class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null  matrix.length == 0  matrix[0].length == 0) { return false; } int row = matrix.length; int col = matrix[0].length; int i = 0; int j = col  1; while (i < row && j >= 0) { int val = matrix[i][j]; if (val == target) { return true; } else if (target < val) { j; // all numbers in that column are even larger } else { i++; // all numbers in that row are even smaller } } return false; } } }

// OJ: https://leetcode.com/problems/searcha2dmatrixii/ // Time: O(M + N) // Space: O(1) class Solution { public: bool searchMatrix(vector<vector<int>>& A, int target) { int M = A.size(), N = A[0].size(), i = 0, j = N  1; while (i < M && j >= 0) { if (A[i][j] == target) return true; if (A[i][j] < target) ++i; else j; } return false; } };

class Solution(object): def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ def binarySearch(nums, target): start, end = 0, len(nums)  1 while start + 1 < end: mid = start + (end  start) / 2 if nums[mid] > target: end = mid elif nums[mid] < target: start = mid else: return True if nums[start] == target: return True if nums[end] == target: return True return False for nums in matrix: if binarySearch(nums, target): return True return False