0001 #define A(k)  ((k) >= UINT_MAX ? INT_MIN : (k) < na ? A[k] : INT_MAX) //假想：向量的两侧分别
0002 #define B(k)  ((k) >= UINT_MAX ? INT_MIN : (k) < nb ? B[k] : INT_MAX) //设有-inf|+inf哨兵
0003 int unionSelect(const Vector<int>& A, const Vector<int>& B, const Rank k) { //两个有序向量
0004    const Rank na = A.size(), nb = B.size();
0005    for (Rank lo = max(k,nb) - nb, hi = min(k,na); ; ) { //以A为主、B为从，反复地猜测、验证
0006       Rank ka = (lo+hi)/2; int sa = A(ka-1), ta = A(ka); //缝隙A = [sa,ta]、B = [sb,tb]
0007       Rank kb = k-ka;      int sb = B(kb-1), tb = B(kb); //始终保证：ka + kb == k
0008       if (tb < sa) hi = ka-1; //若缝隙A完全位于缝隙B之右侧，则A向左折半收缩
0009       else if (ta < sb) lo = ka+1; //若完全位于左侧，则A向右折半收缩
0010       else return min(ta, tb); //两个缝隙迟早必将相交：此时，靠左的右端点即是A+B中的第k大元素
0011    } //每迭代一步，区间宽度hi-lo都会折半，故共需O(log(na))时间
0012 } //不难确认：即便A与B互换，算法依然正确。故更准确地，时间复杂度仅为O(log(min(na,nb)))