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 class Solution {
2 public boolean searchMatrix(int[][] matrix, int target) {
3 // Start typing your Java solution below
4 // DO NOT write main() function
5 if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
6 int i = 0;
7 for(; i < matrix.length; i ++){
8 if(target < matrix[i][0]) {
9 if(i < 1) return false;
10 for(int j = 0; j < matrix[i-1].length; j ++){
11 if(target == matrix[i-1][j]) return true;
12 }
13 return false;
14 }
15 else if(target == matrix[i][0]) return true;
16 }
17 for(int j = 0; j < matrix[i-1].length; j ++){
18 if(target == matrix[i-1][j]) return true;
19 }
20 return false;
21 }
22 }
1 public class Solution {
2 public boolean searchMatrix(int[][] matrix, int target) {
3 // Start typing your Java solution below
4 // DO NOT write main() function
5 if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
6 int start = 0, end = matrix.length - 1, mid = 0;
7 int i = 0, j = 0;
8 while(start <= end){
9 mid = (start + end) / 2;
10 int tmp = matrix[mid][0];
11 if(tmp < target){
12 i = mid;
13 start = mid + 1;
14 }else if(tmp == target) return true;
15 else{
16 end = mid - 1;
17 }
18 }
19 start = 0;
20 end = matrix[0].length - 1;
21 while(start <= end){
22 mid = (start + end) / 2;
23 int tmp = matrix[i][mid];
24 if(tmp < target){
25 j = mid;
26 start = mid + 1;
27 }else if(tmp == target) return true;
28 else{
29 end = mid - 1;
30 }
31 }
32 return false;
33 }
34 }
1 public class Solution {
2 public boolean searchMatrix(int[][] matrix, int target) {
3 // Start typing your Java solution below
4 // DO NOT write main() function
5 if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
6 int row = matrix.length - 1, col = 0;
7 while(row > -1 && col < matrix[0].length){
8 if(matrix[row][col] > target) row --;
9 else if(matrix[row][col] < target) col ++;
10 else return true;
11 }
12 return false;
13 }
14 }