ค่ามัธยฐานของสองอาเรย์ที่เรียงลำดับแล้ว

ทั้งสองลิสต์ถูกเรียงลำดับจากน้อยไปมากแล้ว ให้หาค่ามัธยฐานของตัวเลขทั้งหมดเมื่อนำมารวมกัน; ถ้าจำนวนตัวเลขรวมเป็นจำนวนคู่ ให้ใช้ค่าเฉลี่ยของสองค่ากลาง วิธีการค้นหาแบบ partition ที่ซับซ้อน O(log(m + n)) สามารถทำได้ แต่รับวิธีใดก็ได้ที่ถูกต้องและอยู่ในขอบเขตที่กำหนด

ให้เขียนฟังก์ชัน median_of_two(first, second)

อินพุต

first: ลิสต์ที่เรียงลำดับแล้ว second: ลิสต์ที่เรียงลำดับแล้ว

เอาต์พุต

คืนค่ามัธยฐาน

เงื่อนไข

0 ≤ ความยาว ≤ 100,000; ความยาวรวมของทั้งสองลิสต์ต้องอย่างน้อย 1

ตัวอย่าง

อินพุต:
first = [1, 3]
second = [2]

ผลลัพธ์ที่คาดหวัง:
expected = 2.0

อินพุต:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.0;

อินพุต:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.0;

อินพุต:
first = [1, 2]
second = [3, 4]

ผลลัพธ์ที่คาดหวัง:
expected = 2.5

อินพุต:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.5;

อินพุต:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.5;

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

• From Problems to Performance: Two Decades of Programming Contests in the CCSC Southeast