Guest User

Untitled

a guest
Jan 22nd, 2021
76
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  4.         auto g = [&](int x) {
  5.             return
  6.                 (lower_bound(nums1.begin(), nums1.end(), x) - nums1.begin()) +
  7.                 (lower_bound(nums2.begin(), nums2.end(), x) - nums2.begin());
  8.         };
  9.                
  10.         int L = -1e6, gL = 0;
  11.         int R = +1e6, gR = g(R);
  12.         int seek = (nums1.size() + nums2.size() + 1) / 2;
  13.         if (gR < seek) return R;
  14.         while (R-L > 1) {
  15.             int M = (L+R)/2;
  16.             int gM = g(M);
  17.             if (gM < seek)
  18.                 L = M, gL = gM; else
  19.                 R = M, gR = gM;
  20.         }
  21.        
  22.         if ((nums1.size() + nums2.size()) % 2 == 1)
  23.             return L;
  24.        
  25.         if (gR >= seek+1) return L;
  26.         auto it1 = lower_bound(nums1.begin(), nums1.end(), L+1);
  27.         auto it2 = lower_bound(nums2.begin(), nums2.end(), L+1);
  28.         if (it1 == nums1.end()) return (L + *it2) * 0.5;
  29.         if (it2 == nums2.end()) return (L + *it1) * 0.5;
  30.         return (L + min(*it1, *it2)) * 0.5;
  31.     }
  32. };
  33.  
RAW Paste Data