שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2016 - חיפוש בינארי

רשימה של $n$ מספרים שונים זה מזה תיקרא **רשימה בי-טונית** (bitonic list) אם קיים אינדקס $0 \le k \le n-1$ כך שכל האיברים עד לאינדקס $k$ (כולל) מופיעים בסדר עולה ממש, וכל האיברים החל מאינדקס $k$ מופיעים בסדר יורד ממש. לדוגמא: הרשימות `[1, 2, 3, 4]`, `[-3, 1, 2, 3, 80, 100, 6]` הן רשימות בי-טוניות. **א.** השלימו את מימוש הפונקציה `find_maximum` שמקבלת כקלט רשימה בי-טונית של $n$ מספרים שונים זה מזה, ומחזירה את האינדקס $0 \le k \le n-1$ שבו מתקבל הערך המקסימלי. הפונקציה היא פונקציית מעטפת שמבצעת קריאה לפונקציה רקורסיבית `find_maximum_helper`. על סיבוכיות הזמן במקרה הגרוע להיות $O(\log n)$. ```python def find_maximum(blst): return find_maximum_helper(blst, 0, len(blst)-1) def find_maximum_helper(blst, start, end): n = ______ if n==1: return ______ if n==2: if ______: return ______ else: return ______ ______ if ______: return ______ else: return ______ ``` דוגמת הרצה: ``` >>> find_maximum([-3, 1, 2, 3, 80, 100, 6]) 5 ``` **ב.** השלימו את השורות החסרות בפונקציה `sort_bitonic_list(blst)`, שמקבלת כקלט רשימה בי-טונית blst, ומחזירה רשימה חדשה שאיבריה הם איברי blst ממויינים מקטן לגדול. השתמשו בפונקציה מסעיף א' ובפונקציה `merge` מהכיתה. תזכורת: `merge` מקבלת שתי רשימות ממוינות ויוצרת ביעילות רשימה חדשה ממוינת. ```python def sort_bitonic_list(blst): ______ return merge(______, ______) ``` דוגמת הרצה: ``` >>> sort_bitonic_list([-3, 1, 2, 3, 80, 100, 6]) [-3, 1, 2, 3, 6, 80, 100] ``` **ג.** מיכל מציעה להשתמש בפונקציה `mergesort` (מיון מיזוג) שראינו בכיתה, לצורך מיון רשימה בי-טונית. אמיר חושב ש-mergesort איטי יותר, ועמירם טוען ששתי הפונקציות באותה סיבוכיות. סמנו מי צודק, וציינו מה הסיבוכיות במקרה הגרוע של שתי הפונקציות כתלות באורך הרשימה $n$. 1. מיכל צודקת 2. אמיר צודק 3. עמירם צודק סיבוכיות `sort_bitonic_list`: $O(\text{?})$ סיבוכיות `mergesort`: $O(\text{?})$

רמז: בסעיף א' חשבו על חיפוש בינארי — בדקו את האיבר האמצעי ואת שכנו כדי להחליט לאיזה חצי לרדת. בסעיף ב' מצאו את המקסימום, חלקו לשני חלקים ממויינים, ומזגו. בסעיף ג' השוו את הסיבוכיות של שני הפתרונות.

פתרון: **סעיף א':** ```python def find_maximum(blst): return find_maximum_helper(blst, 0, len(blst)-1) def find_maximum_helper(blst, start, end): n = end - start + 1 if n == 1: return start if n == 2: if blst[start] > blst[end]: return start else: return end mid = (start + end) // 2 if blst[mid] < blst[mid + 1]: return find_maximum_helper(blst, mid + 1, end) else: return find_maximum_helper(blst, start, mid) ``` הרעיון: חיפוש בינארי — בודקים את האיבר האמצעי. אם הוא קטן משכנו הימני, המקסימום בחצי הימני. אחרת, המקסימום בחצי השמאלי (כולל mid). סיבוכיות: $O(\log n)$. **סעיף ב':** ```python def sort_bitonic_list(blst): k = find_maximum(blst) return merge(blst[:k+1], blst[k+1:][::-1]) ``` מוצאים את אינדקס המקסימום $k$. החלק `blst[:k+1]` כבר ממויין בסדר עולה. החלק `blst[k+1:]` בסדר יורד — הופכים אותו ומזגים. סיבוכיות: $O(n)$ עבור merge + $O(\log n)$ עבור find_maximum = $O(n)$. **סעיף ג':** אמיר צודק (תשובה 2). - סיבוכיות `sort_bitonic_list`: $O(n)$ - סיבוכיות `mergesort`: $O(n \log n)$ `sort_bitonic_list` מנצלת את המבנה הבי-טוני ומבצעת merge יחיד ב-$O(n)$, בעוד `mergesort` לא מנצלת את המבנה ועובדת ב-$O(n \log n)$.