#include<bits/stdc++.h>
using namespace std;
int ar[ 100010 ] ;
int max1_c= 0 ,max2_c= 0 ,min1_c= 0 ,min2_c= 0 ;
/*clock_t start1;
clock_t start2;
clock_t start3;
clock_t start4;
clock_t end1;
clock_t end2;
clock_t end3;
clock_t end4;*/
int max_for_one_base_case ( int low, int high)
{
//start1=clock();
if ( low == high)
{
max1_c++ ;
return ar[ low] ;
}
else
{
int mid;
if ( high >= low)
mid = ceil ( ( low + high) / 2 ) ;
max1_c++ ;
int p, q;
p = max_for_one_base_case( low, mid) ;
q = max_for_one_base_case( mid+ 1 , high) ;
return max( p, q) ;
//cout<<"Time for max 1 :"<<(double)(end1-start1)/CLOCKS_PER_SEC<<endl;
}
//end1 =clock();
//cout<<"Time for max 1 :"<<(double)(end1-start1)/CLOCKS_PER_SEC <<endl;
}
int max_for_two_base_case ( int low, int high)
{
//start2=clock();
if ( low == high)
{
max2_c++ ;
return ar[ low] ;
}
else if ( high == low + 1 )
{
max2_c++ ;
return max( ar[ low] , ar[ high] ) ;
}
else
{
int mid;
if ( high >= low)
mid = ceil ( ( low + high) / 2 ) ;
max2_c++ ;
int p, q;
p = max_for_two_base_case( low, mid) ;
q = max_for_two_base_case( mid+ 1 , high) ;
return max( p, q) ;
}
//end2 =clock();
}
int min_for_one_base_case ( int low, int high)
{
//start3=clock();
if ( low == high)
{
min1_c++ ;
return ar[ low] ;
}
else
{
int mid;
if ( high >= low)
mid = ceil ( ( low + high) / 2 ) ;
min1_c++ ;
int p, q;
p = min_for_one_base_case( low, mid) ;
q = min_for_one_base_case( mid+ 1 , high) ;
return min( p, q) ;
}
//end3 =clock();
}
int min_for_two_base_case ( int low, int high)
{
//start4=clock();
if ( low == high)
{
min2_c++ ;
return ar[ low] ;
}
else if ( high == low + 1 )
{
min2_c++ ;
return min( ar[ low] , ar[ high] ) ;
}
else
{
int mid;
if ( high >= low)
mid = ceil ( ( low + high) / 2 ) ;
min2_c++ ;
int p, q;
p = min_for_two_base_case( low, mid) ;
q = min_for_two_base_case( mid+ 1 , high) ;
return min( p, q) ;
}
//end4 =clock();
}
int main( )
{
ofstream out;
ifstream in;
out.open ( "dc.txt" ) ;
//out<< "tamima";
int a;
for ( int i= 1 ; i<= 100000 ; i++ )
{
a= rand ( ) % 10 ;
out<< a<< endl;
}
int k;
cout << "Enter the value of k :" ;
cin >> k;
in.open ( "dc.txt" ) ;
int d;
for ( int i= 0 ; i< k; i++ )
{
in>> d;
ar[ i] = d;
}
clock_t start1= clock ( ) ;
int max1= max_for_one_base_case( 0 ,k- 1 ) ;
clock_t end1= clock ( ) ;
clock_t start2= clock ( ) ;
int max2= max_for_two_base_case( 0 ,k- 1 ) ;
clock_t end2= clock ( ) ;
clock_t start3= clock ( ) ;
int min1= min_for_one_base_case( 0 ,k- 1 ) ;
clock_t end3= clock ( ) ;
clock_t start4= clock ( ) ;
int min2= min_for_two_base_case( 0 ,k- 1 ) ;
clock_t end4= clock ( ) ;
cout << "max1 : " << max1<< " max2 : " << max2<< " min1: " << min1<< " min2: " << min2<< endl;
cout << "max1 counter : " << max1_c<< "\n max2 counter : " << max2_c<< "\n min1 counter : " << min1_c<< "\n min2 counter : " << min2_c<< endl;
//cout<<"Time for max 1 :"<<fabs((double)(end-start)/CLOCKS_PER_SEC) <<endl;
cout << "Time for max 1 :" << fabs ( ( double ) ( end1- start1) / CLOCKS_PER_SEC ) << endl;
cout << "Time for max 2 :" << fabs ( ( double ) ( end2- start2) / CLOCKS_PER_SEC ) << endl;
cout << "Time for min 1 :" << fabs ( ( double ) ( end3- start3) / CLOCKS_PER_SEC ) << endl;
cout << "Time for min 2 :" << fabs ( ( double ) ( end4- start4) / CLOCKS_PER_SEC ) << endl;
// cout<<"Time for max 1 :"<<(double)(end1-start1)/CLOCKS_PER_SEC <<endl;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBhclsxMDAwMTBdOwoKaW50IG1heDFfYz0wLG1heDJfYz0wLG1pbjFfYz0wLG1pbjJfYz0wOwoKLypjbG9ja190IHN0YXJ0MTsKY2xvY2tfdCBzdGFydDI7CmNsb2NrX3Qgc3RhcnQzOwpjbG9ja190IHN0YXJ0NDsKY2xvY2tfdCBlbmQxOwpjbG9ja190IGVuZDI7CmNsb2NrX3QgZW5kMzsKY2xvY2tfdCBlbmQ0OyovCmludCBtYXhfZm9yX29uZV9iYXNlX2Nhc2UgKCBpbnQgbG93LCBpbnQgaGlnaCkKewogICAgLy9zdGFydDE9Y2xvY2soKTsKCiAgICBpZiAobG93ID09IGhpZ2gpCiAgICAgICAgewogICAgICAgICAgICAgbWF4MV9jKys7CiAgICAgICAgICAgIHJldHVybiBhcltsb3ddOwoKICAgICAgICB9CgogICAgZWxzZQogICAgewogICAgICAgIGludCBtaWQ7CgogICAgICAgIGlmIChoaWdoID49IGxvdykKICAgICAgICAgICAgbWlkID0gY2VpbCgobG93ICsgaGlnaCkgLyAyKTsKICAgICAgICBtYXgxX2MrKzsKCiAgICAgICAgaW50IHAsIHE7CgogICAgICAgIHAgPSBtYXhfZm9yX29uZV9iYXNlX2Nhc2UoIGxvdywgbWlkKTsKICAgICAgICBxID0gbWF4X2Zvcl9vbmVfYmFzZV9jYXNlKCBtaWQrMSwgaGlnaCk7CgogICAgICAgIHJldHVybiBtYXgocCwgcSk7CiAgICAgICAgLy9jb3V0PDwiVGltZSBmb3IgbWF4IDEgOiI8PChkb3VibGUpKGVuZDEtc3RhcnQxKS9DTE9DS1NfUEVSX1NFQzw8ZW5kbDsKCiAgICB9CiAgLy9lbmQxID1jbG9jaygpOwogICAgLy9jb3V0PDwiVGltZSBmb3IgbWF4IDEgOiI8PChkb3VibGUpKGVuZDEtc3RhcnQxKS9DTE9DS1NfUEVSX1NFQyA8PGVuZGw7Cgp9CgppbnQgbWF4X2Zvcl90d29fYmFzZV9jYXNlICggaW50IGxvdywgaW50IGhpZ2gpCnsKIC8vc3RhcnQyPWNsb2NrKCk7CiAgICBpZiAobG93ID09IGhpZ2gpCiAgICAgICB7CiAgICAgICAgICAgbWF4Ml9jKys7CiAgICAgICAgIHJldHVybiBhcltsb3ddOwoKICAgICAgIH0KICAgIGVsc2UgaWYgKGhpZ2ggPT0gbG93ICsgMSkKICAgICAgICB7CiAgICAgICAgICAgICBtYXgyX2MrKzsKICAgICAgICAgICAgcmV0dXJuIG1heChhcltsb3ddLCBhcltoaWdoXSk7CgogICAgICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBpbnQgbWlkOwoKICAgICAgICBpZiAoaGlnaCA+PSBsb3cpCiAgICAgICAgICAgIG1pZCA9IGNlaWwoKGxvdyArIGhpZ2gpIC8gMik7CgogICAgICAgIG1heDJfYysrOwoKICAgICAgICBpbnQgcCwgcTsKCiAgICAgICAgcCA9IG1heF9mb3JfdHdvX2Jhc2VfY2FzZSggbG93LCBtaWQpOwogICAgICAgIHEgPSBtYXhfZm9yX3R3b19iYXNlX2Nhc2UoIG1pZCsxLCBoaWdoKTsKCiAgICAgICAgcmV0dXJuIG1heChwLCBxKTsKCiAgICB9CiAvL2VuZDIgPWNsb2NrKCk7Cn0KCgppbnQgbWluX2Zvcl9vbmVfYmFzZV9jYXNlICggaW50IGxvdywgaW50IGhpZ2gpCnsKIC8vc3RhcnQzPWNsb2NrKCk7CiAgICBpZiAobG93ID09IGhpZ2gpCiAgICAgICAgewogICAgICAgICAgICAgbWluMV9jKys7CiAgICAgICAgICAgIHJldHVybiBhcltsb3ddOwoKICAgICAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgaW50IG1pZDsKCiAgICAgICAgaWYgKGhpZ2ggPj0gbG93KQogICAgICAgICAgICBtaWQgPSBjZWlsKChsb3cgKyBoaWdoKSAvIDIpOwogICAgICAgIG1pbjFfYysrOwoKICAgICAgICBpbnQgcCwgcTsKCiAgICAgICAgcCA9IG1pbl9mb3Jfb25lX2Jhc2VfY2FzZSggbG93LCBtaWQpOwogICAgICAgIHEgPSBtaW5fZm9yX29uZV9iYXNlX2Nhc2UoIG1pZCsxLCBoaWdoKTsKCiAgICAgICAgcmV0dXJuIG1pbihwLCBxKTsKCiAgICB9CiAgICAgLy9lbmQzID1jbG9jaygpOwp9CgppbnQgbWluX2Zvcl90d29fYmFzZV9jYXNlICggaW50IGxvdywgaW50IGhpZ2gpCnsKCiAvL3N0YXJ0ND1jbG9jaygpOwogICAgaWYgKGxvdyA9PSBoaWdoKQogICAgICAgIHsKICAgICAgICAgICAgIG1pbjJfYysrOwogICAgICAgICAgICByZXR1cm4gYXJbbG93XTsKCiAgICAgICAgfQogICAgZWxzZSBpZiAoaGlnaCA9PSBsb3cgKyAxKQogICAgICAgIHsKICAgICAgICAgICAgbWluMl9jKys7CiAgICAgICAgICAgIHJldHVybiBtaW4oYXJbbG93XSwgYXJbaGlnaF0pOwoKICAgICAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgaW50IG1pZDsKCiAgICAgICAgaWYgKGhpZ2ggPj0gbG93KQogICAgICAgICAgICBtaWQgPSBjZWlsKChsb3cgKyBoaWdoKSAvIDIpOwoKICAgICAgICBtaW4yX2MrKzsKCiAgICAgICAgaW50IHAsIHE7CgogICAgICAgIHAgPSBtaW5fZm9yX3R3b19iYXNlX2Nhc2UoIGxvdywgbWlkKTsKICAgICAgICBxID0gbWluX2Zvcl90d29fYmFzZV9jYXNlKCBtaWQrMSwgaGlnaCk7CgogICAgICAgIHJldHVybiBtaW4ocCwgcSk7CgogICAgfQoKICAvL2VuZDQgPWNsb2NrKCk7Cn0KCmludCBtYWluKCkKewogICAgb2ZzdHJlYW0gb3V0OwogICAgaWZzdHJlYW0gaW47CiAgICBvdXQub3BlbigiZGMudHh0Iik7CiAgICAvL291dDw8ICAidGFtaW1hIjsKICAgIGludCBhOwogICAgZm9yKGludCBpPTE7IGk8PTEwMDAwMDsgaSsrKQogICAgewogICAgICAgIGE9cmFuZCgpJTEwOwogICAgICAgIG91dDw8YTw8ZW5kbDsKCiAgICB9CgogICAgaW50IGs7CiAgICBjb3V0PDwiRW50ZXIgdGhlIHZhbHVlIG9mIGsgOiI7CiAgICBjaW4+Pms7CiAgICBpbi5vcGVuKCJkYy50eHQiKTsKICAgIGludCBkOwogICAgIGZvcihpbnQgaT0wOyBpPGs7IGkrKykKICAgIHsKICAgICAgICBpbj4+ZDsKICAgICAgICBhcltpXT1kOwoKICAgIH0KICAgIGNsb2NrX3Qgc3RhcnQxPWNsb2NrKCk7CiAgICBpbnQgbWF4MT1tYXhfZm9yX29uZV9iYXNlX2Nhc2UoMCxrLTEpOwogICAgY2xvY2tfdCBlbmQxPWNsb2NrKCk7CgogICAgIGNsb2NrX3Qgc3RhcnQyPWNsb2NrKCk7CiAgICBpbnQgbWF4Mj1tYXhfZm9yX3R3b19iYXNlX2Nhc2UoMCxrLTEpOwogICAgY2xvY2tfdCBlbmQyPWNsb2NrKCk7CgogICAgIGNsb2NrX3Qgc3RhcnQzPWNsb2NrKCk7CiAgICBpbnQgbWluMT1taW5fZm9yX29uZV9iYXNlX2Nhc2UoMCxrLTEpOwogICAgY2xvY2tfdCBlbmQzPWNsb2NrKCk7CgogICAgIGNsb2NrX3Qgc3RhcnQ0PWNsb2NrKCk7CiAgICBpbnQgbWluMj1taW5fZm9yX3R3b19iYXNlX2Nhc2UoMCxrLTEpOwogICAgY2xvY2tfdCBlbmQ0PWNsb2NrKCk7CgogICBjb3V0PDwibWF4MSA6ICI8PG1heDE8PCIgIG1heDIgOiAiPDxtYXgyPDwiICBtaW4xOiAiPDxtaW4xPDwiICBtaW4yOiAiPDxtaW4yPDxlbmRsOwogICAgY291dDw8Im1heDEgY291bnRlciA6ICI8PG1heDFfYzw8IlxubWF4MiBjb3VudGVyIDogIjw8bWF4Ml9jPDwiXG5taW4xIGNvdW50ZXIgOiAgIjw8bWluMV9jPDwiXG5taW4yIGNvdW50ZXIgOiAgIjw8bWluMl9jPDxlbmRsOwoKICAgIC8vY291dDw8IlRpbWUgZm9yIG1heCAxIDoiPDxmYWJzKChkb3VibGUpKGVuZC1zdGFydCkvQ0xPQ0tTX1BFUl9TRUMpIDw8ZW5kbDsKICAgIGNvdXQ8PCJUaW1lIGZvciBtYXggMSA6Ijw8ZmFicygoZG91YmxlKShlbmQxLXN0YXJ0MSkvQ0xPQ0tTX1BFUl9TRUMpIDw8ZW5kbDsKICAgIGNvdXQ8PCJUaW1lIGZvciBtYXggMiA6Ijw8ZmFicygoZG91YmxlKShlbmQyLXN0YXJ0MikvQ0xPQ0tTX1BFUl9TRUMpIDw8ZW5kbDsKICAgIGNvdXQ8PCJUaW1lIGZvciBtaW4gMSA6Ijw8ZmFicygoZG91YmxlKShlbmQzLXN0YXJ0MykvQ0xPQ0tTX1BFUl9TRUMpIDw8ZW5kbDsKICAgIGNvdXQ8PCJUaW1lIGZvciBtaW4gMiA6Ijw8ZmFicygoZG91YmxlKShlbmQ0LXN0YXJ0NCkvQ0xPQ0tTX1BFUl9TRUMpIDw8ZW5kbDsKICAgLy8gY291dDw8IlRpbWUgZm9yIG1heCAxIDoiPDwoZG91YmxlKShlbmQxLXN0YXJ0MSkvQ0xPQ0tTX1BFUl9TRUMgPDxlbmRsOwoKCgp9Cg==