【解法4】优化解：多有序数组折半查找
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法4】优化解：多有序数组折半查找
(1)对A、B数组进行折半查找，设L1、R1为数组A的左右查找边界，L2、R2为B的左右查找边界。数组A[L1至R1]和B[L2\~R2]的中位数，设为a和b，求序列A、B的中位数过程如下：
①若a<b则舍弃序列A中较小的一半A[L1...mid-1]，同时舍弃序列B中较大的一半B[mid+1...R1]。
②若a>=b则舍弃序列A中较大的一半A[mid+1...R1]，同时舍弃序列B中较小的一半B[L1...mid-1]。
重复过程①、②，且需要保证数组A、B中的元素个数相同，如果不同则从长的数组中舍弃一个（因为我们取mid时都是向下取整，所以这里舍弃最小的那个值），直到两个序列中均只含一个元素时为止，较小者即为所求的中位数。本质上不断缩小搜索区间，每次抛弃较小半区，直至剩下的最后一个候选区间。
(2) 伪代码如下：
void ans(int A[], int B[], int n)
{
int mid1, mid2, L1=0, L2=0, R1=n-1, R2=n-1;
}
int ans(int A[], int B[], int n)
{
int L1 = 0, R1 = n - 1, L2 = 0, R2 = n - 1;
while (L1 < R1)
{
int m1 = (L1 + R1) / 2;
int m2 = (L2 + R2) / 2;
if (A[m1] == B[m2]) return A[m1];
if (A[m1] < B[m2])
{
if ((R1 - L1 + 1) % 2 == 0) L1 = m1 + 1;
else L1 = m1;
R2 = m2;
}
else
{
R1 = m1;
if ((R2 - L2 + 1) % 2 == 0) L2 = m2 + 1;
else L2 = m2;
}
}
return min(A[L1], B[L2]);
}
(3) // 时间复杂度：O(logn) 空间复杂度：O(1)
int ans(int A[], int n)
{
for (int i = 0; i < n; i++)
{
int m = 0;
for (int j = 0; j < n; j++)
if (A[i] == A[j]) m++;
if (m > n / 2) return A[i];
}
return -1;
}
(3) // 时间复杂度：O(n²) 空间复杂度：O(1)
void Qsort(int A[], int L, int R)
{
if (L>=R)
return; // 当前区间元素个数<=1则退出
int pivot, i=L, j=R; // i和j是左右两个数组下标移动
pivot=A[L]; // pivot作为基准值参与比较
while (i<j){
while (i<j && A[j]>=pivot)
j--;
while (i<j && A[i]<=pivot)
i++;
if (i<j)
swap(A[i], A[j]); // A[j]<pivot, A[i]>pivot
}
swap(A[L], A[i]); // 将基准值放入他的最终位置
Qsort(A, L, i-1); //递归处理左区间
Qsort(A, i+1, R); //递归处理右区间
}
int ans(int A[], int n)
{
s o m
Qsort(A, 0, n-1);
int t=A[(n-1)/2]; // 主元素只可能是A[(n-1)/2]
int m=0; // m统计当前枚举元素出现次数
for(int i=0; i<n; i++)
if (A[i]==t)
m++;
if (m>n/2)
return t; //找到了主元素
}
int ans(int A[], int n)
{
int j=A[0], t=1; // 取A[0]作为可能主元素
for (int i=1; i<n; i++)
if (A[i]==j) t++;
else
t--;
if (t<0)
{
j=A[i];
t=1;
int m=0; // m统计j出现的次数
for (int i=0; i<n; i++)
if (A[i]==j) m++;
if (m>n/2) return j; // j是主元素，输出j
else return -1; // j不是主元素，输出-1
}
}
(3) // 时间复杂度：O(nlogn) 空间复杂度：O(logn)
int ans(int A[], int n)
{
int count[n]={0}; // count统计数字出现频率
for (int i=0; i<n; i++)
count[A[i]]++; //0<=A[i]<=n，不会越界
for (int j=0; j<n; j++)
if (count[j]>n/2)
return j; //找到了主元素，输出主元素
return -1; // 未找到主元素，输出-1
}
(3) // 时间复杂度：O(n) 空间复杂度：O(n)
(3) // 时间复杂度：O(n) 空间复杂度：O(1)
void ans(int A[], int n)
{
Qsort(A, 0, n - 1);
// 输出 A1: A[0..n/2-1]
// 输出 A2: A[n/2..n-1]，奇数时中间数分给 A2
}
(3) // 时间复杂度：O(nlogn) 空间复杂度：O(logn)
void Quick_Select(int A[], int L, int R, int n)
{
if (L >= R) return;
int i = L, j = R;
int pivot = A[L];
while (i < j)
{
while (i < j && A[j] >= pivot) j--;
while (i < j && A[i] <= pivot) i++;
if (i < j) swap(A[i], A[j]);
}
swap(A[L], A[i]);
if (i == n / 2 - 1) return;
if (n / 2 - 1 < i)
Quick_Select(A, L, i - 1, n);
else
Quick_Select(A, i + 1, R, n);
}
void ans(int A[], int n)
{
Quick_Select(A, 0, n - 1, n);
// 输出 A1: A[0..n/2-1]
// 输出 A2: A[n/2..n-1]，奇数时中间数分给 A2
}
(3)时间复杂度：O(n) // 空间复杂度：O(logn)
void ans(int A[], int n)
{
int L = 0, R = n - 1, target = n / 2 - 1;
while (L < R)
{
int i = L, j = R, pivot = A[L];
while (i < j)
{
while (i < j && A[j] >= pivot) j--;
while (i < j && A[i] <= pivot) i++;
if (i < j) swap(A[i], A[j]);
}
swap(A[L], A[i]);
if (i == target) break;
if (target < i) R = i - 1;
else L = i + 1;
}
// 输出 A1: A[0..n/2-1]
// 输出 A2: A[n/2..n-1]
}