C ++程序使用二进制搜索方法查找两个排序数组的中位数
我们将开发一个C++程序，以使用BinarySearch方法查找两个排序数组的中值。
算法
Begin
Function median() with both the arrays and the start and end indexes of each array, which have two arrays and their respective elements as argument.
A) first calculate the array length as e1 - s1, here e1 nd s1 are the end and start indices.
B) If the length is 2 or 1, calculate the median of arrays according to even or odd length, print the result.
C) Check if both the individual medians are equal, if yes, then print the result.
D) If above two conditions are true then check if m>m2 then the combined median will either be in first half of the first array or in the second half of the second array.
E) If m1<m2 then the combined median will either be in second half of the first array or in the first half of the second array.
F) Call median() recursively, with updated start and end indexes.
End范例程式码
#include<iostream>
using namespace std;
void median(float a1[], int s1, int e1, float a2[], int s2, int e2) {
float m1, m2;
if((e1-s1+1)%2 == 0) {
if(e1-s1 == 1) {
m1 = ((a1[s1]<a2[s2]?a1[s1]:a2[s2])+(a1[e1]>a2[e2]?a1[e1]:a2[e2]))/2;
cout<<m1;
return;
}
m1 = (a1[(e1+s1)/2]+a1[(e1+s1)/2+1])/2;
m2 = (a2[(e2+s2)/2]+a2[(e2+s2)/2+1])/2;
if(m1 == m2 ) {
cout<<m1;
return;
}
else {
if(m1 > m2)
median(a1, s1, (e1+s1)/2+1, a2, (e2+s2)/2, e2);
else
median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2+1);
}
} else {
if(e1-s1 == 0) {
m1 = (a1[s1]+a2[s2])/2;
cout<<m1;
return;
}
m1 = a1[(e1+s1)/2];
m2 = a2[(e2+s2)/2];
if(m1 == m2 ) {
cout<<m1;
return;
}
else {
if(m1 > m2)
median(a1, s1, (e1+s1)/2, a2, (e2+s2)/2, e2);
else
median(a1, (e1+s1)/2, e1, a2, s2, (e2+s2)/2);
}
}
return;
}
int main() {
int n1,n2,i;
cout<<"\nEnter the number of elements for 1st array: ";
cin>>n1;
float a1[n1];
for(i = 0; i < n1; i++) {
cout<<"Enter element for 1st array"<<i+1<<": ";
cin>>a1[i];
}
cout<<"\nEnter the number of elements for 2nd array: ";
cin>>n2;
float a2[n2];
for(i = 0; i < n2; i++) {
cout<<"Enter element for 2nd array "<<i+1<<": ";
cin>>a1[i];
}
cout << "Median is ";
median(a1, 0, n1-1, a2, 0, n2-1) ;
return 0;
}输出结果
Enter the number of elements for 1st array: 5 Enter element for 1st array1: 6 Enter element for 1st array2: 7 Enter element for 1st array3: 9 Enter element for 1st array4: 10 Enter element for 1st array5: 11 Enter the number of elements for 2nd array: 5 Enter element for 2nd array 1: 60 Enter element for 2nd array 2: 70 Enter element for 2nd array 3: 90 Enter element for 2nd array 4: 100 Enter element for 2nd array 5: 110 Median is 35
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短