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.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3return true.
Approach:
The technique is obvious: first compare the last one to find out which line it's on, then iterate through that line to compare (you can use binary search within a line).
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0) return false; if(matrix[0].length == 0) return false; int row = 0; int col = 0; int length = matrix[0].length -1; while(row This siteOriginal articleAll follow "Attribution-NonCommercial-ShareAlike 4.0 License (CC BY-NC-SA 4.0)Please retain the following annotations when sharing or adapting:
Original author:Jake Tao,source:74. Search a 2D Matrix
