Median of Sorted Arrays.cpp

#include <bits/stdc++.h>
using namespace std;
vector <int> vi;
void usingSortfun()
{
    sort(vi.begin(), vi.end());
    cout<<vi[ceil((vi.size()-1)/2)]<<endl;
}

///Algorithm .
///1) Calculate the medians m1 and m2 of the input arrays ar1[] and ar2[] respectively.
///2) If m1 and m2 both are equal then we are done. return m1 (or m2) .
///3) If m1 is greater than m2, then median is present in one of the below two subarrays.
///  a) From first element of ar1 to m1 (ar1[0…|n/2|]) .
///  b) From m2 to last element of ar2 (ar2[|n/2|…n-1]) .
///4) If m2 is greater than m1, then median is present in one of the below two subarrays.
///  a) From m1 to last element of ar1 (ar1[|n/2|…n-1]) .
///  b) From first element of ar2 to m2 (ar2[0…|n/2|])
///5) Repeat the above process until size of both the subarrays becomes 2.
///6) If size of the two arrays is 2 then use below formula to get the median.
///    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2


int median(int *arr1,int *arr2,int n){
int lo1 = 0,hi1 = n-1;
int lo2 = 0,hi2 = n-1;

if(n == 1){
    return (arr1[0] + arr2[0]) >> 1;
}
while(true){
    int m1,m2,median1,median2;
    median1 = arr1[(hi1 + lo1)>>1];
    median2 = arr2[(hi2 + lo2)>>1];
//     5
//     1 3 5 7 9
//     2 4 6 8 10
    m1 = (hi1 + lo1)>>1;
    m2 = (hi2 + lo2)>>1;
    cout<<" m1 "<<m1<<" m2 "<<m2<<endl;

    if(hi1 - lo1 == 1){
        return (max(arr1[lo1] , arr2[lo1]) +
        min(arr1[hi1] , arr2[hi2])) / 2;
    }

    if(median1 == median2)
        return median1;
    if(m1 > m2){
        hi1 = m1;
        lo2 = m2;
    }
    else{
            hi2 = m2;
            lo1 = m1;

    }
}
return 0;
}




//void usingBsearch(int ele)
//{
//    int st = 0;
//    int en = vi.size()-1;
//    int mid = (st + en)/2;
//
//    if(mid > ele)
//    {
//        st = mid + 1;
//    }
//    else if
//}
int main()
{
    int tc;

    cin>>tc;
//    for(int i = 0; i <tc; i++)
//    {
//      int tmp;
//      cin>>tmp;
//      vi.push_back(tmp);
//    }
//    for(int i = 0; i <tc; i++)
//    {
//       int tmp;
//       cin>>tmp;
//       vi.push_back(tmp);
//    }

     int arr[] = {1 , 3 , 5 , 7, 9};
     int arr1[] = {2 , 4 , 6 , 8 , 10};
     median(arr,arr1,5);

    //usingSortfun();
    //usingBsearch();
}