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

נתון מערך מלא במספרים שלמים, שבו כל מספר מופיע **פעמיים ברצף** פרט למספר אחד שמופיע רק פעם אחת. המערך אינו ממוין. לדוגמא, המערכים הבאים מקיימים את התנאי: - `a = {6, 6, 18, 18, -4, -4, 12, 9, 9}` - המספר הבודד הוא 12 באינדקס 6 - `b = {8, 8, -7, -7, 3, 3, 0, 0, 10, 10, 5, 5, 4}` - המספר הבודד הוא 4 באינדקס 12 - `c = {5}` - המספר הבודד הוא 5 באינדקס 0 כתבו שיטה סטטית שמקבלת כפרמטר מערך שמקיים את התנאי הנ"ל, ומחזירה את המספר שמופיע במערך רק פעם אחת. אתם יכולים להניח שהמערך אינו ריק ושהוא מקיים את התנאי, אין צורך לבדוק זאת. חתימת השיטה היא: ```java public static int findSingle(int[] a) ``` **שימו לב:** השיטה שתכתבו צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום. תשובה שאינה יעילה מספיק כלומר, שתהיה בסיבוכיות גדולה יותר מזו הנדרשת לפתרון הבעיה תקבל מעט נקודות בלבד. מה סיבוכיות זמן הריצה של השיטה שכתבתם! הסבירו תשובתכם.

רמז: שימו לב שכל זוג מופיע ברצף — לכן האיבר הבודד תמיד יושב באינדקס זוגי, וניתן לבדוק לכל אינדקס זוגי $i$ האם $a[i]=a[i+1]$ ובכך לדעת באיזה חצי של המערך להמשיך לחפש.

פתרון: ## פתרון: חיפוש בינארי ### תובנת המפתח מכיוון שכל זוג מופיע **ברצף** (שתי פעמים צמודות), המבנה של המערך הוא: $$[x_0, x_0,\; x_1, x_1,\; \ldots,\; \text{single},\; \ldots,\; x_k, x_k]$$ **תצפית קריטית:** האיבר הבודד נמצא תמיד באינדקס **זוגי**. - לפני האיבר הבודד: כל אינדקס זוגי $i$ מקיים $a[i] = a[i+1]$ - אחרי האיבר הבודד: כל אינדקס זוגי $i$ מקיים $a[i] \neq a[i+1]$ לכן ניתן להפעיל **חיפוש בינארי** על האינדקסים הזוגיים! ### השיטה ```java public static int findSingle(int[] a) { int lo = 0, hi = a.length - 1; while (lo < hi) { int mid = (lo + hi) / 2; if (mid % 2 == 1) mid--; // וודא ש-mid זוגי if (a[mid] == a[mid + 1]) { // הזוג שלם — האיבר הבודד נמצא ימינה lo = mid + 2; } else { // הזוג שבור — האיבר הבודד נמצא כאן או שמאלה hi = mid; } } return a[lo]; } ``` ### מעקב על הדוגמאות **דוגמה א':** `{6, 6, 18, 18, -4, -4, 12, 9, 9}`, בודד באינדקס 6 - $lo=0,\; hi=8$: $mid=4$ (זוגי), $a[4]=-4=a[5]$ → $lo=6$ - $lo=6,\; hi=8$: $mid=7$ (אי-זוגי) → $mid=6$, $a[6]=12 \neq a[7]=9$ → $hi=6$ - $lo=hi=6$ → מחזירים $a[6]=12$ ✓ **דוגמה ב':** `{8,8,-7,-7,3,3,0,0,10,10,5,5,4}`, בודד באינדקס 12 - $lo=0,\;hi=12$: $mid=6$, $a[6]=0=a[7]$ → $lo=8$ - $lo=8,\;hi=12$: $mid=10$, $a[10]=5=a[11]$ → $lo=12$ - $lo=hi=12$ → מחזירים $a[12]=4$ ✓ **דוגמה ג':** `{5}` - $lo=hi=0$ מיד → מחזירים $a[0]=5$ ✓ --- ## סיבוכיות זמן הריצה **סיבוכיות הזמן: $O(\log n)$** **הסבר:** בכל איטרציה של לולאת ה-`while`, טווח החיפוש $[lo, hi]$ מתמצמץ לפחות בחצי. ספציפית, מגיעים ל-$mid$ זוגי ואז: - אם `a[mid] == a[mid+1]`: $lo \leftarrow mid+2$, כלומר הטווח מתמצמץ כמעט בחצי - אם `a[mid] != a[mid+1]`: $hi \leftarrow mid$, כלומר הטווח מתמצמץ לפחות בחצי מספר האיטרציות הוא $O(\log n)$, וכל איטרציה מבצעת מספר קבוע של פעולות. **סיבוכיות המקום: $O(1)$** — משתמשים רק בכמה משתנים קבועים ($lo$, $hi$, $mid$) ללא תלות בגודל הקלט. **זוהי הסיבוכיות האופטימלית:** האיבר הבודד יכול להופיע בכל אחד מ-$\frac{n+1}{2}$ מקומות אפשריים, ולכן נדרשות לפחות $\log_2\!\left(\frac{n+1}{2}\right) = O(\log n)$ השוואות.