PROBLEM DESCRIPTION
Given a matrix of size n x m, where every row and column is sorted in increasing order, and a number x. Find whether element x is present in the matrix or not.
SOLUTION
APPROACH 1
Iterate row wise and use binary search in each row to look for element x. We can add a small optimization to do this search only if x is between first and last number in the current row.
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
33
34
35
36
37
38
39
40
41
42
class Solution
{
static boolean search(int matrix[][], int n, int m, int x)
{
for(int r=0; r<n; r++){
if(x >= matrix[r][0] && x <= matrix[r][m-1]){
if(binarysearch(matrix[r], x))
return true;
}
}
return false;
}
static boolean binarysearch(int[] arr, int x){
int l = 0;
int r = arr.length-1;
while(l<=r){
int m = (l+r)/2;
if(arr[m] == x)
return true;
if(x > arr[m]){
l = m+1;
}else{
r = m-1;
}
}
return false;
}
}