1 #include <iostream>  2 #include <cstdlib>  3 #include <cmath>  4 #include <algorithm>  5   6 using namespace std;  7   8 class Solution {  9 public: 10     double findMedianSortedArrays(int A[], int m, int B[], int n) { 11         double ma = 0; 12         double mb = 0; 13  14         bool empty_a = A == NULL || m < 1; 15         bool empty_b = B == NULL || n < 1; 16          17         if (!empty_a) ma = (A[(m - 1) / 2] + A[m/2]) / 2.0; 18         if (!empty_b) mb = (B[(n - 1) / 2] + B[n/2]) / 2.0; 19          20         if (empty_a && empty_b) { // will this happen ? 21             return 0; 22         } else if (empty_a) { 23             return mb; 24         } else if (empty_b) { 25             return ma; 26         } 27          28         double low = 0, high = 0; 29  30         if (ma > mb) { 31             low = mb, high = ma; 32         } else if (ma < mb) { 33             low = ma, high = mb; 34         } else { 35             return ma; 36         } 37          38         double precise = 0.1; 39         double mv = 0; 40         int total = m + n; 41         int half  = total / 2; 42         bool declared = false; 43         while(high - low > precise) { 44             mv = (high + low) / 2.0; 45             int* pa = lower_bound(A, A + m, mv); 46             int* pb = lower_bound(B, B + n, mv); 47             int lh = (pa - A) + (pb - B); 48  49             if (lh < half) {        // the median assumed is too small, so increase it 50                 low = mv; 51             } else if (lh > half) { // the median assumed is too big, so decrease it 52                 high= mv; 53             } else { 54                 declared = true; 55                 // divided into odd/even case. should re-calculate the mv 56                 // for even case median calculated from two adjacent numbers in 57                 // the merged array, we assume that one is mmore and the other 58                 // is mless (median = (mmore + mless) / 2.0 ) 59                 int mmore = 0; 60                 // find bigger number to compute median for even case. 61                 if (pa == A + m && pb == B + n) { 62                     // should not happen; 63                     cout<<"[1]should not happen"<<endl; 64                 } else if (pa == A + m) { 65                     mmore = *pb; 66                 } else if (pb == B + n) { 67                     mmore = *pa; 68                 } else { 69                     if (*pa < *pb) { 70                         mmore = *pa; 71                     } else { 72                         mmore = *pb; 73                     } 74                 } 75                  76                 // for odd case. the mv is equal to value of mmore 77                 if (half * 2 != total) { 78                     mv = mmore; 79                     break; 80                 } 81                  82                 // find samller number to compute median for even case. 83                 pa--, pb--; 84                 int mless = 0; 85                 if (pa < A && pb < B) { 86                     // should not happen 87                     cout<<"[2]should not happen"<<endl; 88                 } else if (pa < A) { 89                     mless = *pb; 90                 } else if (pb < B) { 91                     mless = *pa; 92                 } else { 93                     if (*pb > * pa) { 94                         mless = *pb; 95                     } else { 96                         mless = *pa; 97                     } 98                 } 99                 mv = (mless + mmore) / 2.0;100                 break;101             }102         }103         if (declared) { // median value is on the boundary104             return mv;105         }106         if (fabs(mv - ma) < fabs(mv - mb)) {107             return ma;108         } else {109             return mb;110         }111     }112 };113 114 int main() {115     Solution s;116     int A[] = {1, 1};117     int B[] = {1, 2};118     int m = sizeof(A) / sizeof(A[0]);119     int n = sizeof(B) / sizeof(B[0]);120     121     cout<<s.findMedianSortedArrays(A, m, B, n)<<endl;122     system("pause");123     return 0;124 }

 1 class Solution { 2 public: 3     double findMedianSortedArrays(int A[], int m, int B[], int n) { 4         int ia = 0, ib = 0; 5         int it = -1; 6         int im = (m + n - 1) / 2; 7         int val= 0; 8  9         bool empty_a = A == NULL || m < 1;10         bool empty_b = B == NULL || n < 1;11         12         while (!empty_a && ia < m && !empty_b && ib < n && it < im) {13             if (A[ia] < B[ib]) {14                 val = A[ia++];15             } else {16                 val = B[ib++];17             }18             ++it;19         }20         21         while (!empty_a && ia < m && it < im) {22             val = A[ia++];23             it++;24         }25         while (!empty_b && ib < n && it < im) {26             val = B[ib++];27             it++;28         }29         if ((m + n) & 1) {30             return val;31         } else {32             int val2 = 0;33             if ((empty_a || ia >= m) && (empty_b || ib >= n)) {34                 // should not happen35             } else if (empty_a || ia >= m) {36                 val2 = B[ib];37             } else if (empty_b || ib >= n) {38                 val2 = A[ia];39             } else {40                 val2 = A[ia] > B[ib] ? B[ib] : A[ia];41             }42             return (val + val2) / 2.0;43         }44     }45 };