 # Easy to understand C++ solution with comments . Time Complexity: O(min(log m, log n)) Space Complexity: O(1)

#1
``````double Solution::findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
int x=A.size(), y=B.size();
//if A length is greater then switch them so that A is smaller than B
if(x>y) return findMedianSortedArrays(B,A);
int start=0,end=x;  //two array hence don't use end=x-1 as smaller array may be empty
while(start<=end){
int partitionX = start + (end-start)/2;
int partitionY =(x+y+1)/2 - partitionX;

//if partitionX is 0 it means nothing is there on left side. Use -INF for minX
//if partitionX is length of input then there is nothing on right side. Use +INF for maxX
//update min and max which are left/right neighbouring values around partition
int minX = (partitionX==0)? INT_MIN:A[partitionX-1];
int maxX = (partitionX==x)? INT_MAX:A[partitionX];

int minY = (partitionY==0)? INT_MIN:B[partitionY-1];
int maxY = (partitionY==y)? INT_MAX:B[partitionY];

if(minX<=maxY && minY<=maxX){
//We have partitioned array at correct place
if((x+y)%2 == 0)
return ((double)(max(minX,minY)+min(maxX,maxY)))/2;
else
return (double)max(minX,minY);
}
else if(minX>maxY)
//we are too far on right side for partitionX. Go on left side.
end = partitionX-1;
else
//we are too far on left side for partitionX. Go on right side.
start = partitionX+1;
}
//We can come here only**strong text** if input arrays were not sorted.
return -1;
}``````