pranay_teja
10/5/2018 - 8:25 AM

## Search in Matrix rows

``````#include<bits/stdc++.h>
using namespace std;

// #Searching
// Search in Matrix rows
/*

Test Case:
1
3 4
1 2 3 5
1 3 5 6
6 7 8 9
5
Output:
4
3
-1
*/

int BinSearch(vector<int> a, int x, int l,int r);
vector< vector<int> > solve(vector< vector<int> >a, int x);
int find(vector<int> a, int x);

int main(){
int t;
cin>>t;
while(t--){
int r,c;
cin>>r>>c;
vector< vector<int> > a(r);
for(int i=0;i<r;i++){
a[i].resize(c);
}
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin>>a[i][j];
}
}
int x;
cin>>x;
vector< vector<int> > ans=solve(a,x);
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans[i].size();j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}

}
return 0;
}

vector< vector<int> > solve(vector< vector<int> >a, int x){
vector< vector<int> >ans(a.size());
for(int i=0;i<a.size();i++){
ans[i].push_back(find(a[i],x));
}
return ans;
}

int find(vector<int> a, int x){
return BinSearch(a,x,0,a.size()-1);
}
int BinSearch(vector<int> a, int x, int l,int r){
if(l<=r){
if(l==r){
if(a[l]==x){
return l+1;	// l is index, l+1 is position
}else{
return -1;
}
}
int m=l+((r-l)/2);
if(a[m]==x){
return m+1;	// m is index, m+1 is position
}else if(a[m]<x){
return BinSearch(a,x,m+1,r);
}else{
return BinSearch(a,x,l,m-1);
}
}else{
return -1;
}
}

``````