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

שאלה 2 (25 נקודות): נתון מערך `arr` באורך $3 < n$ שמכיל רצף של איברים עוקבים מסדרה חשבונית. תת-סדרה אחת של הסדרה החשבונית (באורך של איבר אחד לפחות) חסרה. תזכורת: סדרה חשבונית היא סדרה של מספרים, שבה ההפרש בין כל שני איברים עוקבים הוא קבוע: $d = a_{n+1} - a_n$, כאשר $a_n$ הוא האיבר ה-$n$-י בסדרה. ממשו את הפונקציה ```c int FindMissingIndex(int arr[], int n) ``` שמוצאת את האינדקס במערך בו היה אמור להופיע האיבר הראשון בתת-הסדרה החסרה. דוגמה: עבור המערך $\{22,24,26,32,34,36,38,40\}$ הפונקציה תחזיר $3$, כי זהו האינדקס בו היה אמור להופיע האיבר הבא אחרי המספר $26$ בסדרה החשבונית. דרישות: • ממשו את הפונקציה בסיבוכיות זמן $O(\log n)$. אם לא עמדתם בדרישות הסיבוכיות, אנא ציינו כאן את הסיבוכיות שהגעתם אליה: זמן ____________ מקום נוסף _______

רמז: שימו לב שאם לא חסר כלום עד אינדקס $i$, מתקיים $\text{arr}[i] = \text{arr}[0] + i \cdot d$ בדיוק. תכונה זו מונוטונית — נסו להשתמש בה לחיפוש בינארי לאחר שתקבעו את $d$ מתוך שלושת האיברים הראשונים.

פתרון: **רעיון מרכזי:** נשתמש ב**חיפוש בינארי** כדי למצוא את האינדקס הראשון שבו הערך במערך סוטה מהערך הצפוי בסדרה. **שלב 1 – מציאת ההפרש $d$** מכיוון שיש רק פער אחד רציף, לפחות שניים מתוך שלושת האיברים הראשונים `arr[0]`, `arr[1]`, `arr[2]` הם עוקבים בסדרה המקורית. לכן: $$d = \min\bigl(\text{arr}[1]-\text{arr}[0],\ \text{arr}[2]-\text{arr}[1]\bigr)$$ **שלב 2 – תנאי העקביות** אם לא חסר כלום עד אינדקס $i$, אז הערך הצפוי הוא: $$\text{expected}(i) = \text{arr}[0] + i \cdot d$$ ברגע שהפער מופיע, כל האיברים מאותו מקום ואילך יסטו מהערך הצפוי. **שלב 3 – חיפוש בינארי** מחפשים את **האינדקס הקטן ביותר** $i$ שבו $\text{arr}[i] \neq \text{arr}[0] + i \cdot d$: - אם $\text{arr}[\text{mid}] = \text{arr}[0] + \text{mid} \cdot d$ — הפער נמצא **מימין**, נעביר את $lo = \text{mid}+1$. - אחרת — הפער נמצא **כאן או שמאלה**, נעביר $hi = \text{mid}$. **מימוש:** ```c int FindMissingIndex(int arr[], int n) { // שלב 1: מציאת d מתוך שלושת האיברים הראשונים int d1 = arr[1] - arr[0]; int d2 = arr[2] - arr[1]; int d = (d1 < d2) ? d1 : d2; // שלב 2: חיפוש בינארי – אינדקס ראשון שסוטה מהצפוי int lo = 0, hi = n - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] == arr[0] + mid * d) { lo = mid + 1; // עד כאן הכל תקין, הפער מימין } else { hi = mid; // הפער כאן או שמאלה } } return lo; } ``` **אימות עם הדוגמה:** $\{22,24,26,32,34,36,38,40\}$, $n=8$ - $d = \min(2, 2) = 2$ - חיפוש בינארי: $lo=0, hi=7 \Rightarrow mid=3$: צפוי $22+6=28 \neq 32$ $\Rightarrow hi=3$ - $lo=0, hi=3 \Rightarrow mid=1$: צפוי $22+2=24=24$ $\Rightarrow lo=2$ - $lo=2, hi=3 \Rightarrow mid=2$: צפוי $22+4=26=26$ $\Rightarrow lo=3$ - $lo=hi=3$, מוחזר **3** ✓ **סיבוכיות:** - **זמן:** $O(\log n)$ — חיפוש בינארי על מערך באורך $n$. - **מקום נוסף:** $O(1)$ — רק משתנים בודדים.