שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2022 - הפרד ומשול

שאלה 3 – חציון של צמד רשימות ממוינות תזכורת: החציון של רישימה סדורה, הנתון המסכמול שמול שלם הראשונה המחקבלת הרשימה $(2,9,7,2,3)$ (קיביוליות הרשימה המחקבלת $(2,9,7,2,3)$ שבמצמד שנבמד הראשונה המחקבלת (לפי סדר): $Median(2,9,7,2,3)=3$. החציון הנתון שיקום קדקוד הרשימה וגם חציון נתון כשלא הרשימה זוג, אחר מחצוי סכום קדקודים שני הרשימה המחקבלת. למשל, $Median(1,2,4,9)=2$. הבעיה: בנתונו גישה לשתי רישימות ממוינות, שכל אחד מהם מיוחד מאוד למצוא רישימה סדוקה ממוינות של $n$ מספרים. עלינו למצוא את החציון של הדגמה $2n$ המספרים, ובתנאי שלכל בגישה לממלוקח $2n$ של המסקנה לתחום פונקציה מקדקודים בעסקום קדקודים לשליוטה לבקיצועות במדרוג $m$ של המספרים $2n$ תתחום אלגוריתם לשליוטה בעסקום קדקודים לתחום פונקציה מקדקודים בעסקום קדקודים לשליוטה. תתחום אלגוריתם לעדכון סדור לגרימות סדרות פונקציה מקדקודים בעסקום קדקודים לתחום פונקציה מקדקודים בעסקום קדקודים לשליוטה בעסקום קדקודים לשליוטה בעסקום קדקודים לשליוטה: "כתחום המספרום של כל מסכום לסדור המסכום של הסדור שלהם מקדקודים בעסקום קדקודים לתחום פונקציה מקדקודים בעסקום קדקודים לשליוטה בעסקום קדקודים לשליוטה בעסקום קדקודים לשליוטה".

רמז: חשבו כיצד לחלק את $2n$ האיברים לשתי קבוצות שוות בגודלן, $n$ איברים "קטנים" ו-$n$ איברים "גדולים", כך שכל איבר בקבוצה אחת קטן או שווה לכל איבר בקבוצה השנייה. ניתן למצוא חלוקה כזו ביעילות באמצעות חיפוש בינארי.

פתרון: הבעיה היא למצוא את החציון של איחוד שתי רשימות ממוינות, A ו-B, כל אחת בגודל $n$. איחוד הרשימות הוא רשימה ממוינת בגודל $2n$. על פי ההגדרה בשאלה, החציון של רשימה בגודל $m$ הוא האיבר במקום ה-$\{\lfloor(m+1)/2\rfloor\}$. עבור $m=2n$, החציון הוא האיבר במקום ה-$n$. לכן, מטרתנו היא למצוא את האיבר ה-$n$ הקטן ביותר באיחוד של A ו-B. פתרון נאיבי יהיה למזג את שתי הרשימות לרשימה אחת בגודל $2n$ בסיבוכיות זמן של $O(n)$, ואז לבחור את האיבר במקום ה-$n$. אנו נציג אלגוריתם יעיל יותר בסיבוכיות $\boldsymbol{O(\log n)}$. הרעיון המרכזי הוא להשתמש ב**חיפוש בינארי** לא כדי למצוא ערך מסוים, אלא כדי למצוא את ה**חלוקה** הנכונה של האיברים. אנו מחפשים חלוקה של $2n$ האיברים לשתי קבוצות של $n$ איברים כל אחת - קבוצה "שמאלית" שתכיל את $n$ האיברים הקטנים ביותר, וקבוצה "ימנית" שתכיל את $n$ האיברים הגדולים ביותר. החציון שאנו מחפשים יהיה האיבר הגדול ביותר בקבוצה השמאלית. נניח שהקבוצה השמאלית מורכבת מ-$i$ האיברים הראשונים של A ומ-$j$ האיברים הראשונים של B. מכיוון שהקבוצה השמאלית צריכה להכיל $n$ איברים, מתקיים $\boldsymbol{i+j=n}$. כדי שהחלוקה תהיה נכונה, כל איבר בקבוצה השמאלית חייב להיות קטן או שווה לכל איבר בקבוצה הימנית. מכיוון שהרשימות A ו-B ממוינות, התנאי הזה מתקיים אם ורק אם שני התנאים הבאים מתקיימים בו זמנית (בשימוש באינדקסים מ-1 עד $n$): 1. האיבר הגדול ביותר מהחלק של A בקבוצה השמאלית קטן או שווה לאיבר הקטן ביותר מהחלק של B בקבוצה הימנית. כלומר: $\boldsymbol{A[i] \le B[j+1]}$ 2. האיבר הגדול ביותר מהחלק של B בקבוצה השמאלית קטן או שווה לאיבר הקטן ביותר מהחלק של A בקבוצה הימנית. כלומר: $\boldsymbol{B[j] \le A[i+1]}$ מכיוון ש-$j=n-i$, שני התנאים תלויים רק ב-$i$. מטרתנו היא למצוא $i$ (בטווח $[0, n]$) המקיים את שני התנאים. נוכל למצוא את $i$ באמצעות חיפוש בינארי על טווח הערכים האפשריים שלו. **האלגוריתם:** נבצע חיפוש בינארי על האינדקס $i$ בטווח $[0, n]$. בכל איטרציה: 1. נבחר $i$ באמצע טווח החיפוש הנוכחי. נחשב $j = n-i$. 2. נבדוק את תנאי החלוקה: - אם $\boldsymbol{A[i] > B[j+1]}$: האיבר $A[i]$ גדול מדי כדי להיות בקבוצה השמאלית. זה אומר שבחרנו יותר מדי איברים מ-A (כלומר, $i$ גדול מדי). לכן, נמשיך את החיפוש בטווח הקטן יותר של $i$. - אם $\boldsymbol{B[j] > A[i+1]}$: האיבר $B[j]$ גדול מדי. זה אומר שבחרנו יותר מדי איברים מ-B, כלומר $j$ גדול מדי ו-$i$ קטן מדי. לכן, נמשיך את החיפוש בטווח הגדול יותר של $i$. - אם שני התנאים אינם מתקיימים, מצאנו את ה-$i$ הנכון. החלוקה נכונה. החציון הוא האיבר ה-$n$ הכולל, שהוא האיבר המקסימלי בקבוצה השמאלית: $\boldsymbol{\max(A[i], B[j])}$. יש לטפל במקרי קצה: כאשר $i=0$ או $i=n$ (ואז $j=n$ או $j=0$), נתייחס לאיברים "מחוץ למערך" כאל $\infty$ או $-\infty$ לפי הצורך. לדוגמה, אם $i=0$, אז $A[i]$ הוא $-\infty$ ו-$A[i+1]$ הוא $A[1]$. אם $i=n$, אז $A[i]$ הוא $A[n]$ ו-$A[i+1]$ הוא $\infty$. **סיבוכיות:** החיפוש הבינארי מתבצע על טווח בגודל $n+1$. בכל צעד, אנחנו מקטינים את טווח החיפוש בחצי. כל צעד לוקח זמן קבוע $O(1)$. לכן, סיבוכיות הזמן הכוללת של האלגוריתם היא $\boldsymbol{O(\log n)}$.$\blacksquare$