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 = 5return true.
Given target = 20return false.
Approach:
This problem requires a specific technique. We choose the top-right corner point and compare the values. If the value is larger, we move down; if smaller, we move to the right. (Because starting from that point, values below are always greater than those to the left, and values to the left are always less than those to the right.)
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 = matrix[0].length -1; while(row=0){ if(matrix[row][col] == target){ return true; } if(matrix[row][col] > target){ col --; } else if(matrix[row][col] < target){ row++; } } return false; } } 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:「240. Search a 2D Matrix II」
