Problem Description
Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length;
int n=matrix[0].length;
int l=0;
int r=m*n-1;
while(l<=r){
int mid = (l+r)/2;
int row = mid/n; // 5/4 and 5%4
int column = mid%n;
int x = matrix[row][column];
if(x == target) return true;
if(x < target){
l=mid+1;
}else{
r=mid-1;
}
}
return false;
}
}