09.19算法第二章上机实践报告

标签：bsp   最大   程序   输入   代码   并集   执行   end   一个   

算法第二章上机实践报告

https://edu.cnblogs.com/campus/gdwywm/se1803/homework/7608 

 

1.实践题目

7-3 两个有序序列的中位数

https://pintia.cn/problem-sets/1173827583729741824/problems/1173827629514764290

2.问题描述

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A ?0 ?? ,A ?1 ?? ,?,A ?N−1 ?? 的中位数指A ?(N−1)/2 ?? 的值,即第⌊(N+1)/2⌋个数（A ?0 ?? 为第1个数）。  输入格式:  输入分三行。第一行给出序列的公共长度N（0

输入样例1:

 

5

1 3 5 7 9

2 3 4 5 6

输出样例1:

 

4

输入样例2:

 

6

-100 -10 1 1 1 1

-50 0 2 3 4 5

输出样例2:

 

1

 

3.算法描述

 

二分搜索两个有序数组，每次取两个数组的中位数a[mida],b[midb]并比较，二者相等时找到题目所求的中位数并返回，否则将数组缩小一半

a[mida]

当搜索的区间长度为偶数时，下界加一

因为两个数组初始时等长，while循环里最后一次是a,b数组是长度为2的连续有序区间,[la,ra]与[lb,rb],因为区间的元素是偶数个,跳出循环时la==ra,lb==rb 分别指向两个长度为2的子区间的最大值，取min为所求的中位数。

 

代码：

 

#include

using namespace std;

const int maxn=1e5+10;

int a[maxn],b[maxn],n;

int solve()

{

    int la=0,ra=n-1,lb=0,rb=n-1,mida,midb;

    while(la

        mida=(la+ra)>>1;

        midb=(lb+rb)>>1;

        if(a[mida]==b[midb]){

            return a[mida];

        }

        else if(a[mida]

    

            if((la+ra)%2==0){

                la=mida;

                rb=midb;

            }

            else{

                la=mida+1;

                rb=midb;

            }

            

        }

        else{

            //a[mida]>b[midb]

    

            if((lb+rb)%2==0){

                lb=midb;

                ra=mida;

            }

            else{

                ra=mida;

                lb=midb+1;

            }

        }

        

    }

    return min(a[la],b[lb]);

}

int main()

{

    cin>>n;

    for(int i=0;i

        cin>>a[i];

    for(int i=0;i

        cin>>b[i];

    cout

    return 0;

}

 

 

4.算法时间及空间复杂度分析

 

主函数执行的语句为给数组赋值，时间复杂度和空间复杂度均为O(n)

solve函数里每次加法运算、移位运算、比较值的大小和赋值，执行logn次，时间复杂度为O(logn),空间复杂度为O(1)

 

5.心得体会

本次上机实践加深了对二分思想的理解，巩固了设计程序的知识，在分析和实践的过程里体会了二分在思维和时间复杂度上的优越性。

09.19算法第二章上机实践报告

标签：bsp   最大   程序   输入   代码   并集   执行   end   一个   

原文地址：https://www.cnblogs.com/biekanle/p/11552438.html