9.1.cpp

清华文件 考研用. Distribution of this memo is unlimite

//保证没有抄袭他人程序！
//00448246 雷加贝

#include <iostream>
using namespace std;

#define MAXN 100

int n;
int a[MAXN], b[MAXN];//a,b对应序列A,B

//函数返回a,b中较大者
int bigger(int a, int b)
{
	if (a > b) return a; else return b;
}

int search(int s, int t)//查找区间[s,t]
{
	int i = (s + t) / 2;//i取区间中位数
	int j = (n - i - 2);//由i+j+2=n可得
	if (s == t || a[i + 1] >= b[j] && b[j + 1] >= a[i])	return bigger(b[j], a[i]);//若区间收缩为点，或者i已经为满足条件的点，则返回
	if (a[i + 1] < b[j]) return search(i, t); else return search(s, i);//折半继续查找
}

void main()
{
	int i;
	cin >> n;
	for (i = 0; i < n; i ++)
		cin >> a[i];//输入A
	for (i = 0; i < n; i ++)
		cin >> b[i];//输入B
	if (a[0] > b[n - 1]) cout << b[n - 1]; 
	else if (b[0] > a[n - 1]) cout << a[n - 1]; //判断A[n-1]或者B[n-1]是否为中位数
	else cout << search(0, n - 1) << endl;//在A的全区间内折半查找
}