PROBLEM DESCRIPTION
Given a matrix of integers A of size N x M and an integer B. Write an efficient algorithm that searches for integer B in matrix A.
This matrix A has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than or equal to the last integer of the previous row.
Return 1 if B is present in A, else return 0.
NOTE: Rows are numbered from top to bottom, and columns are from left to right.
SOLUTION
This problem is same as: Search a 2D Matrix
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
32
public class Solution {
public int searchMatrix(int[][] A, int B) {
int n = A.length;
int m = A[0].length;
int l=0;
int r=(n*m)-1;
while(l<=r){
int mid = (l+r)/2;
int i = mid/m;
int j = mid%m;
if(A[i][j] == B){
return 1;
}else if(A[i][j] < B){
l = mid+1;
}else{
r = mid-1;
}
}
return 0;
}
}