我在网上遇到了一个示例，用于查找 2 个排序数组的中位数。但是我很难理解为什么每次都需要对它进行分区，如果它已经排序。另外，如果它没有找到 2 个相等的中位数会怎样？
将不胜感激一些澄清。谢谢
http://www-scf.usc.edu/~csci303/cs303hw3solutions.pdf
Problem 3 (9.3-8):
Let X[1, . . . , n] and Y [1, . . . , n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y .
Solution 3:
Two-List-Median(X, p, q, Y, s, t)
mx ← Index-Of-Median(X, p, q)
my ← Index-Of-Median(Y, s, t)
X[mx] ↔ X[q]
Y [my] ↔ Y [t]
Partition(X, p, q)
Partition(Y, s, t)
if X[mx] = Y [my]
return X[mx]
else if X[mx] > Y [my]
return Two-List-Median(X, p, mx − 1, Y, my + 1, t)
else
return Two-List-Median(X, mx + 1, q, Y, s, my − 1)