求两个等长升序序列的中位数（二分）

题目：
给两个长度均为N的升序序列，求两个序列的所有元素的中位数。定义一个长度为L的升序序列S，其 $L / 2$ 位置的数为中位数。

思路：
PS：这里网上挺多***括标准答案都是取靠中间的前一个作为中位数，但根据题目的意思似乎是靠中间的后一个才是中位数吧？

很直观地能想到合并数组直接 $O (1)$ 查找，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$
对于这样地问题还可以这样思考：既然合并前有序，合并后中位数显然是合并前的某一半边，然后就可以判断一下两个升序序列一半的数字进行比较，就能够确定中位数一定不在某一半边，那么就剔除它，每次两个序列都能从各自当前的序列剔出约一半的数字，于是就能够得到一个二分近似物，利用迭代式时间复杂度 $O (l o g 2^{n})$ ，空间复杂度 $O (1)$ ；利用递归式时间复杂度与空间复杂度均为 $O (l o g 2^{n})$ 。

Code：

#include <bits/stdc++.h>
using namespace std;

//迭代二分
int search_m(int A[], int B[], int n) {
  int a_left, b_left, a_right, b_right, a_mid, b_mid;
  a_left = b_left = 0;
  a_right = b_right = n - 1;
  while ( a_left < a_right || b_left < b_right ) {
    a_mid = a_left + (a_right - a_left + 1 >> 1);
    b_mid = b_left + (b_right - b_left + 1 >> 1);
    if ( A[a_mid] == B[b_mid] ) return A[a_mid];
    else if ( A[a_mid] < B[b_mid] ) {
      b_right -= a_mid - a_left;
      a_left = a_mid;
    } else {
      a_right -= b_mid - b_left;
      b_left = b_mid;
    }
  }
  return A[a_left] > B[b_left] ? A[a_left] : B[b_left];
}

//递归版二分
int search_m2(int A[], int B[], int n) {
  if ( n == 1 ) return A[n-1] > B[n-1] ? A[n-1] : B[n-1];
  int mid = n >> 1; //向上取整
  if ( A[mid] == B[mid] ) return A[mid];
  if ( A[mid] < B[mid] ) return search_m2(A+mid, B, n-mid);
  return search_m2(A, B+mid, n-mid);
}

int main() {
  int n, i;
  int A[105],B[105];
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &A[i]);
  for (i = 0; i < n; i++) scanf("%d", &B[i]);
  sort(A, A+n); sort(B, B+n);
  printf("%d\n", search_m2(A, B, n));
  return 0;
}