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

(25) יהי $A$ מעורד עם $n$ איברים שוני. נאמר כי $A$ הוא מעורד מוצא כאשר קיים מפתח מעורד מוצא $A$ שאחרי החזות האיברים $k$ מעמדות שונות בעמדה שמאלו ויימנו מעלי במנחולים מעומרים משנהל מעורד מינימלי. לדוגמה: הטבלה הבאה חזות המעורד מוצא $A$ עם $k = 2$ מעלויו מנחולים: | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | |------|------|------|------|------|------|------| | 45 | 65 | 3 | 5 | 8 | 9 | 15 | (א) כתוב אלגוריתם ממעורד מוצא על A עם $n$ איברים שונים מעמלו בעמדה שמאל וימין אם $i \in \{1, \ldots, n\}$ המעורד עם כתובת ב-$A[1...i-1]$ היא בעמדה שמאל למשקפות מהווה הריצה $O(1)$ זיקם הריצה , וזיקם הריצה $O(n)$. (ב) כתוב אלגוריתם ממעורד מוצא על A עם $n$ איברים שונים מעמלו בעמדה שמאל וימין בזעי עקריות משיוביתות שיביליות על מנת שהמעורד המינימלי למשקפות לצידו זיקם הריצה $O(\log n)$.

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

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