fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. double findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
  6.     // Do not write main() function.
  7.     // Do not read input, instead use the arguments to the function.
  8.     // Do not print the output, instead return values as specified
  9.     // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
  10.     int nA = A.size(),  nB = B.size();
  11.     if(nA > nB) return findMedianSortedArrays(B, A);
  12.     int total = nA + nB;
  13.     int start = 0 , end = nA; 
  14.     while(start <= end)
  15.     {
  16.         int partA = (start + end)/2;
  17.         int partB = (total + 1)/2 - partA;
  18.         double leftMaxA = (partA > 0)? A[partA - 1] : INT_MIN ;
  19.         double rightMinA = (partA < nA)? A[partA] : INT_MAX ;
  20.         double leftMaxB = (partB > 0)? B[partB - 1] : INT_MIN ;
  21.         double rightMinB = (partB < nB)? B[partB] : INT_MAX ;
  22.         cout << partA <<","<< partB <<","<< leftMaxA <<","<< leftMaxB <<","<< rightMinA <<","<< rightMinB <<"\n";
  23.         if(leftMaxA <= rightMinB && leftMaxB <= rightMinB)
  24.         {
  25.             // return ((total % 2) == 0)? (double)(max(leftMaxA, leftMaxB) + min(rightMinA, rightMinB))/2.0 : (double)max(leftMaxA, leftMaxB)
  26.             if((total % 2) == 0)
  27.                 return  (double)(max(leftMaxA, leftMaxB) + min(rightMinA, rightMinB))/2.0 ;
  28.             else
  29.                 return (double)max(leftMaxA, leftMaxB);
  30.         }
  31.         else if(leftMaxA > rightMinB)
  32.         {
  33.             end = partA - 1;
  34.         }
  35.         else
  36.         {
  37.             start = partA + 1;   
  38.         }
  39.     }
  40. }
  41.  
  42.  
  43. int main() {
  44.  
  45. const vector<int> A = {-40, -25, 5, 10, 14, 28, 29, 48};
  46. const vector<int> B = {-48, -31, -15, -6, 1, 8};
  47.  
  48. double x = findMedianSortedArrays(A, B);
  49. cout << "Result: " << x << endl;
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3,4,-15,10,-6,14
Result: 2
https://ideone.com/cvj6kl
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!