LOVE BABBAR DSC MATRIX QUESTION 3- SOLUTION

 LOVE BABBAR DSC MATRIX - SOLUTION

Q3) FIND MEDIAN IN ROW WISE SORTED MATRIX

int median(vector<vector<int>> &matrix, int r, int c){

        int min_e = INT_MAX, max_e = INT_MIN;

        //find min, max elements in matrix

        for(int i = 0; i < r; i++){

            if(min_e > matrix[i][0])

                min_e = matrix[i][0];

                

            if(max_e < matrix[i][c-1])

                max_e = matrix[i][c-1];

        }

        //binary search

        int target = (r*c + 1)/2;

        while(min_e < max_e){

            int mid = min_e + (max_e - min_e)/2;

            int place = 0;

            for(int i = 0; i < r; i++){

                place += upper_bound(matrix[i].begin(), matrix[i].begin()+c, mid) - matrix[i].begin();

            }

            if(place < target)

                min_e = mid+1;

            else 

                max_e = mid;

        }

        return min_e;

    }