• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest Jan 21st, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. double findMedianSortedArrays(int A[], int m, int B[], int n) {
2.         return findMedianHelper2(A, m, B, n, max(0, (m-n)/2), min(m-1, (m+n)/2));
3.     };
4.
5.     double findMedianHelper2(const int A[], const int m, const int B[], const int n, const int l, const int r) {
6.         if (l > r) return findMedianHelper2(B, n, A, m, max(0, (n-m)/2), min(n-1, (m+n)/2));
7.         int i = (l+r)/2;
8.         int j = (m+n)/2-i;
9.
10.         assert(i >= 0 && i <= m && j >= 0 && j <= n);
11.         int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
12.         int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
13.         int Ai = ((i == m) ? INT_MAX : A[i]);
14.         int Bj = ((j == n) ? INT_MAX : B[j]);
15.
16.         if (Ai < Bj_1) return findMedianHelper2(A, m, B, n, i+1, r);
17.         if (Ai > Bj) return findMedianHelper2(A, m, B, n, l, i-1);
18.
19.         if (((m+n) % 2) == 1) return A[i];
20.         return (max(Ai_1, Bj_1) + Ai) / 2.0;
21.     };
22.
23. IF m - n < 0 THEN
24.     l = 0
25. ELSE l = (m - n) / 2
26.
27. IF (m + n) / 2 > m - 1 THEN
28.     r = m -1
29. ELSE r = (m + n) / 2
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top