נתונים שני מערכים חד־ממדיים באורך זהה, a ו־b, המכילים מספרים שלמים.

סעיף א (20 נקודות)

כתבו שיטה סטטית המקבלת כפרמטרים את שני המערכים a ו־b, ומוצאת זוג איברים — אחד מ־a ואחד מ־b — כך שההפרש בערך מוחלט ביניהם הוא הקטן ביותר מבין כל ההפרשים האפשריים.

השיטה צריכה:

• להחזיר את ההפרש הקטן ביותר.
• להדפיס (בתוך השיטה) את זוג האיברים שמהם נוצר ההפרש הקטן ביותר.

חתימת השיטה:

public static int smallestDiffPair(int[] a, int[] b)

---

סעיף ב (5 נקודות)

כתבו שיטה סטטית המקבלת כפרמטרים את שני המערכים a ו־b, ומוצאת זוג איברים — אחד מ־a ואחד מ־b — כך שההפרש בערך מוחלט ביניהם הוא הגדול ביותר מבין כל ההפרשים האפשריים.

השיטה צריכה:

• להחזיר את ההפרש הגדול ביותר.
• להדפיס (בתוך השיטה) את זוג האיברים שמהם נוצר ההפרש הגדול ביותר.

חתימת השיטה:

public static int biggestDiffPair(int[] a, int[] b)

---

דוגמה:

אם המערכים הם:

a = 1 5 -2 2 6 2
b = 0 1 2 3 4 0 8 3 7

אז:

• השיטה smallestDiffPair תחזיר את הערך 1, ותדפיס את האיברים 3 --- 2 או 7 --- 6.
• השיטה biggestDiffPair תחזיר את הערך 10, ותדפיס את האיברים -2 --- 8.

---

שימו לב:

• שתי השיטות צריכות להיות יעילות ככל הניתן:

  • גם מבחינת סיבוכיות זמן.
  • וגם מבחינת סיבוכיות מקום.

• פתרון שאינו יעיל מספיק (בסיבוכיות גבוהה יותר מזו הנדרשת) יקבל מעט נקודות בלבד.

• סיבוכיות המקום לא חייבת להיות קבועה, אך צריכה להיות מינימלית ככל הניתן.

• ציינו מהי סיבוכיות זמן הריצה ומהי סיבוכיות המקום של כל שיטה שכתבתם.

• הסבירו את תשובתכם.