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;
	}
}