2dpeak.cpp

//2d peak
// algo 1, a combination of binary search along columns with brute force to find global maximum
#include<bits/stdc++.h>
using namespace std;
int m,n;
// to find global maximum in a given column
// helper function
int peakone(int **arr,int j,int n){
	int max = 0;
	for(int i=1;i<n;i++){
		cout<<arr[i][j]<<"\t";
		if(arr[max][j]<arr[i][j])max = i;
	}
	return max;
}
int recursivepeaktwod(int **arr,int start,int end,int m,int n){
	int midcol = start + (end-start)/2;
	int maxElemMidCol = peakone(arr,midcol,n);
	if((midcol==0 || arr[midcol-1][end]<arr[midcol][maxElemMidCol])&&(midcol==n-1 || arr[midcol+1][maxElemMidCol]<arr[midcol][maxElemMidCol]))
		return arr[midcol][maxElemMidCol];
  else if (midcol>0 && arr[midcol-1][maxElemMidCol]>arr[midcol][maxElemMidCol])
    return recursivepeaktwod(arr,start,midcol-1,m,n);
	else return recursivepeaktwod(arr,midcol+1,end,m,n);
}
int main(){
	cin>>m; 
	cin>>n;
	int **arr;
	arr = new int*[m];
	for(int i = 0;i<m;i++)arr[i]= new int[n]; 
	for(int i= 0; i<m;i++)
		for(int j= 0 ;j<n;j++)
			cin>>arr[i][j];
	
	for(int i= 0; i<m;i++){
		for(int j= 0 ;j<n;j++)
			cout<<arr[i][j]<<"\t";
		cout<<endl;
	}
	cout<<recursivepeaktwod(arr,0,m-1,m,n)<<endl;
	return 0;
}