שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2013 - חיפוש בינארי

בעיית החיפוש הפרבולי נתון משרן $A$ בודל בן $n$ שלמים שונים וקטנים לפדיר מחדש את איברי המשרן כך שתתקיימו: • לכל $1 \le i \le \lfloor \frac{n}{2} \rfloor$: $A[i] \le A[i-1]$ • לכל $n \ge i \ge \lfloor \frac{n}{2} \rfloor + 1$: $A[i] \le A[i+1]$ משרן המקימים שונים וקטנים הייצו הפרבולי; לדוגמה המשרן המימצא הבטא המשרן הבא: | 29 | 25 | 21 | 16 | 9 | 2 | 4 | 8 | 11 | 15 | א. האמור אלגוריתם ממימטן את המשרן בעיניית הדירושה לפנחרון בעיית החיפוש הפרבולי, בדומה למאתי המשרן של $O(n)$. הטלה האלגוריתם תחנו לטוב זמן התחנו לטוב ריצות אלגוריתמים. ב. בנדול משוררות בגדל, כלומר, תנו האמור אלגוריתם תחנו לטוב זמן התחנו לטוב ריצות אלגוריתמים לפרבול.

רמז: ניתן לשפר את סיבוכיות החיפוש מלינארית ($O(n)$) ללוגריתמית ($O(\log n)$) על ידי ניצול המבנה הפרבולי של המערך ושימוש בגישת 'הפרד ומשול', בדומה לחיפוש בינארי.

פתרון: השאלה עוסקת במציאת האיבר המינימלי במערך בעל מבנה "פרבולי", כלומר, מערך שהאיברים בו יורדים עד לנקודת מינימום מסוימת, ואז עולים. נציג שני אלגוריתמים לפתרון בעיה זו. **א. אלגוריתם בסיבוכיות $O(n)$** ניתן למצוא את האיבר המינימלי במערך באמצעות **סריקה לינארית** פשוטה. האלגוריתם יאתחל משתנה שישמור את הערך המינימלי שנמצא עד כה, ויעבור על כל איברי המערך כדי למצוא את הערך הקטן ביותר. **אלגוריתם:** 1. אתחל משתנה `min_val` לערך של האיבר הראשון במערך, `A[0]`. 2. עבור כל איבר `A[i]` במערך (כאשר `i` רץ מ-1 עד `n-1`): - אם `A[i] < min_val`, עדכן: `min_val = A[i]`. 3. לאחר סיום המעבר על כל המערך, `min_val` יכיל את הערך המינימלי. **ניתוח סיבוכיות:** האלגוריתם מבצע מעבר יחיד על כל $n$ איברי המערך. בכל צעד מתבצעת פעולת השוואה אחת ומספר קבוע של פעולות נוספות. לכן, **סיבוכיות זמן הריצה** הכוללת היא $O(n)$. **סיבוכיות המקום** היא $O(1)$, מכיוון שלא נדרש זיכרון נוסף התלוי בגודל הקלט. **ב. אלגוריתם משופר בסיבוכיות $O(\log n)$** התכונה המיוחדת של המערך הפרבולי מאפשרת לנו להשתמש באלגוריתם יעיל יותר המבוסס על **חיפוש בינארי**. הרעיון הוא שבכל שלב נוכל להסתכל על האיבר האמצעי ועל שכנו כדי להחליט באיזה חצי של המערך נמצא המינימום, ובכך לצמצם את מרחב החיפוש בחצי. גישה זו היא דוגמה לאסטרטגיית **הפרד ומשול**. **אלגוריתם:** האלגוריתם יחפש באופן רקורסיבי את המינימום בתחום `[left, right]`. `FindMin(A, left, right)`: 1. **תנאי עצירה:** אם `left == right`, החזר את `A[left]`, מכיוון שזהו האיבר היחיד שנותר בתחום. 2. חשב את האינדקס האמצעי: `mid = floor((left + right) / 2)`. 3. **בדיקת האיבר האמצעי ושכנו:** - אם `A[mid] < A[mid + 1]`: אנו נמצאים בחלק העולה של המערך, או ש-`A[mid]` הוא המינימום עצמו. פירוש הדבר שהמינימום חייב להימצא בחלק השמאלי של המערך (כולל `mid`). לכן, נמשיך את החיפוש בתחום `[left, mid]` על ידי קריאה רקורסיבית: `FindMin(A, left, mid)`. - אם `A[mid] > A[mid + 1]`: אנו נמצאים בחלק היורד של המערך. פירוש הדבר שהמינימום חייב להימצא בחלק הימני של המערך (לא כולל `mid`). לכן, נמשיך את החיפוש בתחום `[mid + 1, right]` על ידי קריאה רקורסיבית: `FindMin(A, mid + 1, right)`. הקריאה הראשונית לאלגוריתם תהיה `FindMin(A, 0, n-1)`. **ניתוח סיבוכיות:** בכל קריאה רקורסיבית, גודל הבעיה (מספר האיברים בתחום החיפוש) נחצה בערך. **נוסחת הנסיגה** לזמן הריצה היא $T(n) = T(n/2) + O(1)$, כאשר $O(1)$ מייצג את הזמן הנדרש לחישוב האינדקס האמצעי והשוואה אחת. על פי משפט המאסטר (Master Theorem), או על ידי פתירת הרקורסיה, הפתרון הוא $T(n) = O(\log n)$. לכן, **סיבוכיות הזמן** של האלגוריתם המשופר היא $O(\log n)$. **סיבוכיות המקום** היא $O(\log n)$ עבור ערימת הרקורסיה (ניתן לממש את האלגוריתם באופן איטרטיבי ולהגיע לסיבוכיות מקום של $O(1)$). $\blacksquare$