median-of-two-sorted-arrays.cc

// Median of Two Sorted Arrays
class Solution {
public:
  double findMedianSortedArrays(vector<int> &a, vector<int> &b) {
    int m = a.size(), n = b.size(), i = 0, j = 0, k = m+n-1 >> 1;
    while (k > 0) {
      int p = k-1 >> 1;
      if (j+p >= n || i+p < m && a[i+p] < b[j+p])
        i += p+1;
      else
        j += p+1;
      k -= p+1;
    }
    int s = j >= n || i < m && a[i] < b[j] ? a[i++] : b[j++];
    return m+n & 1 ? s : (j >= n || i < m && a[i] < b[j] ? s+a[i] : s+b[j]) * 0.5;
  }
};