4. 寻找两个正序数组的中位数 #

class Solution {
public:
  double slice_mid(vector<int> v, int from, int to) {
    auto size = (from - to + 1);
    auto mid = from + (to - from) / 2; // 靠下的中点
    if (size % 2 == 0) {
      return (double(v[mid]) + double(v[mid + 1])) / 2.0;
    } else {
      return v[mid];
    }
  }
  double findMedianSortedArrays(vector<int> &a, vector<int> &b) {
    if (a.size() > b.size()) {
      return findMedianSortedArrays(b, a);
    }

    int al = 0, ar = a.size() - 1;
    int bl = 0, br = b.size() - 1;

    while (true) {
      auto size_a = ar + 1 - al;
      auto size_b = br + 1 - bl;
      // 如果两个都只剩一个，则返回平均值
      if (size_a == 1 && size_b == 1) {
        return (double(a[ar]) + double(b[br])) / 2;
      }
      // 如果某个数组空，则返回另一个的中位数
      if (size_a == 0) {
        return slice_mid(b, bl, br);
      }
      if (size_b == 0) {
        return slice_mid(a, al, ar);
      }

      // 从小端删除左边
      if (a[al] <= b[bl]) {
        al++;
      } else {
        bl++;
      }
      // 从大端删除右边
      if (a[ar] > b[br]) {
        ar--;
      } else {
        br--;
      }
    }
  }
};

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int tot = nums1.length + nums2.length;
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    // i和j：分别表示当前考虑的n1和n2的起始索引。
    // k：要找的第k小的元素。
    int find(int[] nums1, int i, int[] nums2, int j, int k) {
        if (nums1.length - i > nums2.length - j) return find(nums2, j, nums1, i, k);
        if (i >= nums1.length) return nums2[j + k - 1];
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        } else {
            int si = Math.min(i + (k / 2), nums1.length); // nums1 左半段中点
            int sj = j + k - (k / 2); // nums2 右半段中点
            if (nums1[si - 1] > nums2[sj - 1]) { // 比较的是第一段的最后一个元素和第二段的前一个元素
                return find(nums1, i, nums2, sj, k - (sj - j));
            } else {
                return find(nums1, si, nums2, j, k - (si - i));
            }
        }
    }
}