נגדיר: החציון median הוא המספר האמצעי ברשימה מסודרת של מספרים. כך שמספר המספרים הגדולים ממנו ברשימה שווה למספר המספרים הקטנים ממנו ברשימה. כאשר מספר המספרים ברשימה הוא זוגי, נהוג להגדיר את החציון כממוצע בין שני המספרים האמצעיים ברשימה.
דוגמאות:
ברשימה {1, 4, 5, 7, 20} - החציון הוא 5 יש ברשימה שני מספרים גדולים ממנו (1 ו- 4) ושני מספרים קטנים ממנו (7 ו- 20).
ברשימה {1, 4, 5, 7, 20, 28} החציון הוא 6 שהוא הממוצע בין 5 ו-7.
בהינתן שני מערכים חד-ממדיים בגודל n מלאים במספרים שלמים, ממוינים בסדר לא יורד. יש להחזיר את החציון של המספרים הנמצאים בשני המערכים.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
a = [1, 12, 15, 26, 38], b = [12, 13, 18, 30, 45]
16
הסבר: אחרי מיזוג שני המערכים למערך ממוין אחד נקבל: {1, 12, 12, 13, 15, 18, 26, 30, 38, 45} בגלל שהמערך המיוזג הוא באורך זוגי (10), החציון הוא הממוצע בין שני המספרים האמצעיים שבו. המספרים האמצעיים במערך הם 15 ו-18. הממוצע ביניהם הוא (15 + 18) / 2 = 16 (לא 16.5 בגלל שהחלקה במספרים שלמים).
a = [1, 3], b = [2, 2]
2
הסבר: אחרי מיזוג: [1, 2, 2, 3]. החציון הוא 2
a = [1, 2], b = [3, 4]
2
הסבר: אחרי מיזוג: [1, 2, 3, 4]. החציון הוא (2 + 3) / 2 = 2
a = [0, 0], b = [0, 0]
0
הסבר: אחרי מיזוג: [0, 0, 0, 0]. החציון הוא (0 + 0) / 2 = 0
a = [1, 3, 5, 7], b = [2, 4, 6, 8]
4
הסבר: אחרי מיזוג: [1, 2, 3, 4, 5, 6, 7, 8]. החציון הוא 4
a = [10, 20, 30], b = [15, 25, 35]
22
הסבר: אחרי מיזוג: [10, 15, 20, 25, 30, 35]. החציון הוא (20 + 25) / 2 = 22
a = [1, 2, 7, 9], b = [3, 6, 7, 8]
6
הסבר: אחרי מיזוג: [1, 2, 3, 6, 7, 7, 8, 9]. החציון הוא (7 + 6) / 2 = 6
a = [100, 100, 100, 100, 100], b = [1, 2, 3, 4, 5]
52
הסבר: אחרי מיזוג: [1, 2, 3, 4, 5, 100, 100, 100, 100, 100]. החציון הוא (5 + 100) / 2 = 52
קלט:
a = [1, 12, 15, 26, 38], b = [12, 13, 18, 30, 45]
הפלט המבוקש:
16