leetcode

0 class Solution {

1 public:

2 double findMedianSortedArrays(const vector<int> &nums1, const vector<int> &nums2) {

3 const int n1 = nums1.size(), n2 = nums2.size(), n = n1 + n2;

4 if (n % 2)

5 return binary(nums1, nums2, n / 2, 0, n1 - 1, 0, n2 - 1);

6 else

7 return (binary(nums1, nums2, n / 2 - 1, 0, n1 - 1, 0, n2 - 1) +

8 binary(nums1, nums2, n / 2, 0, n1 - 1, 0, n2 - 1)) /

9 2.0;

10 }

11

12 double binary(const vector<int> &nums1, const vector<int> &nums2, int k, int s1, int e1, int s2, int e2) {

13 if (s1 > e1) return nums2[k - s1];

14 if (s2 > e2) return nums1[k - s2];

15

16 const int m1 = s1 + (e1 - s1) / 2;

17 const int m2 = s2 + (e2 - s2) / 2;

18

19 if (m1 + m2 < k) {

20 return nums1[m1] > nums2[m2] ? binary(nums1, nums2, k, s1, e1, m2 + 1, e2)

21 : binary(nums1, nums2, k, m1 + 1, e1, s2, e2);

22 } else {

23 return nums1[m1] > nums2[m2] ? binary(nums1, nums2, k, s1, m1 - 1, s2, e2)

24 : binary(nums1, nums2, k, s1, e1, s2, e2 - 1);

25 }

26 return -1;

27 }

28 };