שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 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) ``` **שימו לב:** השיטה שתכתבו צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום. תשובה שאינה יעילה מספיק כלומר, שתהיה בסיבוכיות גדולה יותר מזו הנדרשת לפתרון הבעיה תקבל מעט נקודות בלבד. מה סיבוכיות זמן הריצה של השיטה שכתבתם! הסבירו תשובתכם.

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

פתרון: **רעיון הפתרון:** נשתמש ב-**חיפוש בינארי**. התובנה המרכזית: לפני המספר הבודד, כל זוג מתחיל באינדקס **זוגי**. אחרי המספר הבודד, כל זוג מתחיל באינדקס **אי-זוגי**. ```java public static int findSingle(int[] a) { int lo = 0, hi = a.length - 1; while (lo < hi) { int mid = (lo + hi) / 2; // make mid even if (mid % 2 == 1) mid--; if (a[mid] == a[mid + 1]) lo = mid + 2; // single is to the right else hi = mid; // single is at mid or to the left } return a[lo]; } ``` **סיבוכיות זמן:** $O(\log n)$ - בכל צעד מחצים את תחום החיפוש. **סיבוכיות מקום:** $O(1)$ - רק משתנים מקומיים. **הסבר:** בכל שלב בודקים את האינדקס הזוגי mid. אם `a[mid] == a[mid+1]` אז הזוג שלם, כלומר המספר הבודד נמצא מימין. אחרת, המספר הבודד נמצא ב-mid או משמאלו.