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

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

רמז: סעיף א': בדקו את היחס בין האיבר הראשון $A[1]$ לבין האיבר $A[i]$. מה ניתן להסיק מכך על מיקום ה'שבר' במערך המעגלי? סעיף ב': מספר ההזזות תלוי במיקום האיבר הקטן ביותר. השתמשו בחיפוש בינארי כדי למצוא אותו ביעילות.

פתרון: ## חלק א' — בדיקת מיקום המקסימום ב-$O(1)$ **תצפית מבנית:** במערך ממוין מעגלי עם הזזה $k>0$, קיים "נקודת שבירה" יחידה: $$A[k+1] < A[k+2] < \cdots < A[n] < A[1] < A[2] < \cdots < A[k]$$ כלומר, כל איברי הצד השמאלי (אינדקסים $1\dots k$) גדולים מ-$A[n]$, וכל איברי הצד הימני קטנים מ-$A[1]$. **האלגוריתם:** ``` MAX_LOCATION(A, n, i): if A[1] < A[n]: // k=0, המערך ממוין כבר, מקסימום ב-A[n] if i == n: return 0 else: return 1 // כאן A[1] > A[n], קיימת הזזה k > 0 if A[i] < A[1]: // A[i] בצד הימני (i > k), המקסימום נמצא ב-A[1..k] ⊆ A[1..i] return 0 // A[i] ≥ A[1], כלומר i בצד השמאלי (i ≤ k) if i < n and A[i] < A[i+1]: // עדיין לא הגענו לנקודת השבירה return 1 else: // A[i] > A[i+1] או i=n ← A[i] הוא המקסימום return 0 ``` **נכונות:** האלגוריתם מבצע $O(1)$ השוואות בלבד (ניגוש לאינדקסים קבועים). **דוגמה:** על $A = [45, 65, 3, 5, 8, 9, 12]$ עם $i=2$: $A[1]=45 > A[7]=12$, $A[2]=65 \geq A[1]=45$, ו-$A[2]=65 > A[3]=3$ ← מחזיר **0** ✓. עבור $i=1$: $A[1]=45<A[2]=65$ ← מחזיר **1** ✓. --- ## חלק ב' — מציאת מספר ההזזות ב-$O(\log n)$ **רעיון:** מספר ההזזות $k$ שווה למיקום האיבר הגדול ביותר. האיבר הגדול ביותר הוא האיבר היחיד הגדול יותר מ-$A[n]$ שנמצא הכי ימינה בין כל האיברים הגדולים מ-$A[n]$. **תכונה לחיפוש בינארי:** לכל $j \in \{1,\dots,n\}$: $$A[j] > A[n] \iff j \leq k$$ לכן נחפש בחיפוש בינארי את הגבול הימני של קבוצה זו. **האלגוריתם:** ``` FIND_ROTATIONS(A, n): if A[1] < A[n]: // המערך ממוין כבר return 0 lo ← 1, hi ← n while lo < hi: mid ← ⌊(lo + hi + 1) / 2⌋ if A[mid] > A[n]: lo ← mid // נקודת השבירה נמצאת ב-[mid, hi] else: hi ← mid - 1 // נקודת השבירה נמצאת ב-[lo, mid-1] return lo // lo = k ``` **נכונות:** בכל איטרציה נשמר **אינווריאנט**: $k \in [\mathtt{lo}, \mathtt{hi}]$. - אם $A[\mathtt{mid}] > A[n]$ אז $\mathtt{mid} \leq k$, לכן נעדכן $\mathtt{lo} \leftarrow \mathtt{mid}$. - אם $A[\mathtt{mid}] \leq A[n]$ אז $\mathtt{mid} > k$ (כי $A[n]$ עצמו שייך לצד הימני), לכן $\mathtt{hi} \leftarrow \mathtt{mid}-1$. הלולאה מסתיימת כאשר $\mathtt{lo}=\mathtt{hi}=k$. $\blacksquare$ **מעקב על הדוגמה:** $A = [45, 65, 3, 5, 8, 9, 12]$, $n=7$, $A[7]=12$: | $\mathtt{lo}$ | $\mathtt{hi}$ | $\mathtt{mid}$ | $A[\mathtt{mid}]$ | פעולה | |:---:|:---:|:---:|:---:|:---| | 1 | 7 | 4 | 5 < 12 | $\mathtt{hi}\leftarrow 3$ | | 1 | 3 | 2 | 65 > 12 | $\mathtt{lo}\leftarrow 2$ | | 2 | 3 | 3 | 3 < 12 | $\mathtt{hi}\leftarrow 2$ | | 2 | 2 | — | — | מחזיר **2** ✓ | **סיבוכיות:** בכל איטרציה מחצים את הטווח $[\mathtt{lo}, \mathtt{hi}]$, לכן זמן הריצה הוא $O(\log n)$. $\blacksquare$