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

class Solution {
  int KthSmallest(vector<int> &V1, vector<int> &V2, int K) {
    int Size1 = V1.size(), Size2 = V2.size();
    int I = 0, J = 0;
    while (true) {
      // To get Kth smallest means that K is ORDER, not INDEX, so in fact 1 is
      // the identity here. And if we want to use K to INDEX, we need to convert
      // it to 0-indexed, i.e. minus by one.
      if (I == Size1)
        return V2[J + (K - 1)];
      if (J == Size2)
        return V1[I + (K - 1)];
      if (K == 1)
        return std::min(V1[I], V2[J]);

      int Half = K / 2;
      // Comparison happens INSIDE the to-be-eliminated part.
      int NewI = std::min(I + Half, Size1) - 1;
      int NewJ = std::min(J + Half, Size2) - 1;
      if (V1[NewI] < V2[NewJ]) {
        // Eliminate elements at the front. Keep in mind that comparison happens
        // INSIDE, so we need to add one here to convert INDEX to SIZE.
        K -= NewI - I + 1;
        I = NewI + 1;
      } else {
        K -= NewJ - J + 1;
        J = NewJ + 1;
      }
    }
  }
public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int Total = nums1.size() + nums2.size();
    if (Total % 2 == 0)
      return (KthSmallest(nums1, nums2, Total / 2) +
              KthSmallest(nums1, nums2, Total / 2 + 1)) / 2.;
    else
      return KthSmallest(nums1, nums2, Total / 2 + 1);
  }
};

class Solution {
  int KthSmallest(vector<int> &A, vector<int> &B, int K) {
    int SizeA = A.size(), SizeB = B.size();
    // i and j are 0-indexed; K is 1-indexed.
    int i = 0, j = 0;
    while (true) {
      // Check for corner cases.
      if (i == SizeA)
        return B[j + (K - 1)];
      if (j == SizeB)
        return A[i + (K - 1)];
      // Check if we have counted to the last number.
      if (K == 1)
        return std::min(A[i], B[j]);

      // Make Next pointers no larger than end().
      int NextI = std::min(SizeA, i + K / 2);
      int NextJ = std::min(SizeB, j + K / 2);
      // Compare INCLUSIVE ranges, and update K correspondingly.
      if (A[NextI - 1] < B[NextJ - 1]) {
        K -= NextI - i;
        i = NextI;
      } else {
        K -= NextJ - j;
        j = NextJ;
      }
    }
  }
public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int TotalSize = nums1.size() + nums2.size();
    if (TotalSize % 2 == 0)
      return (KthSmallest(nums1, nums2, TotalSize / 2) +
              KthSmallest(nums1, nums2, TotalSize / 2 + 1)) / 2.;
    else
      return KthSmallest(nums1, nums2, TotalSize / 2 + 1);
  }
};