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 = 3
, return true
.
1 public boolean searchMatrix(int[][] matrix, int target) { 2 // Start typing your Java solution below 3 // DO NOT write main() function 4 int M = matrix.length; 5 if(M == 0){ 6 return false; 7 } 8 int N = matrix[0].length; 9 if(N == 0){ 10 return false; 11 } 12 13 int row = 0, col = N - 1; 14 while(row < M && col >= 0){ 15 if(matrix[row][col] == target){ 16 return true; 17 } else if(matrix[row][col] > target){ 18 col--; 19 } else{ 20 row++; 21 } 22 } 23 return false; 24 }