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

השיטה הבאה אמורה למצוא איבר x בתוך מערך חד-ממדי a בעזרת חיפוש בינרי. המערך מלא במספרים שלמים מסודרים בסדר לא-יורד. ```java public static void f(int[] a, int x) { int i, j, k; i = 0; j = a.length - 1; do { k = (i + j) / 2; if (a[k] < x) i = k; else j = k; } while (a[k] != x && i < j); if (a[k] == x) System.out.println("x is in the array"); else System.out.println("x is not in the array"); } ``` סעיף ב: (5 נקודות) איזה שינוי (אם בכלל) צריך לעשות כדי לתקן את השיטה f שלעיל? סמנו תשובתכם על השאלון. 1. לשנות את תנאי ה-if הראשון לתנאי הזה: `if (a[k] < x) i = k-1; else j = k+1;` 2. לשנות את תנאי ה-if הראשון לתנאי הזה: `if (a[k] < x) i = k+1; else j = k-1;` 3. לשנות את תנאי ה-if הראשון לתנאי הזה: `if (a[k] <= x) i = k; else j = k;` 4. לשנות את תנאי ה-while לתנאי הזה: `while ((a[k] == x) && (i < j));` 5. אין צורך לשנות כלום. הקוד תקין.

רמז: בדקו מה קורה לגבולות `i` ו-`j` כאשר `k = i`: האם הטווח $[i,j]$ מצטמצם בהכרח בכל איטרציה? חפשו תיקון שמבטיח שהטווח תמיד יצטמצם ב-**לפחות אחד**.

פתרון: ## ניתוח הבאג בקוד המקורי **הבעיה המרכזית** בקוד המקורי היא אפשרות ל**לולאה אינסופית**. נבדוק מה קורה עם `i=0, j=1`: $$k = \lfloor(0+1)/2\rfloor = 0$$ אם `a[0] < x`, אז מתבצע `i = k = 0` — כלומר `i` **לא השתנה**! תנאי הלולאה `a[k] != x && i < j` עדיין מתקיים ← לולאה אינסופית. הבאג: כאשר `i = k` (ובאופן סימטרי `j = k`), הטווח $[i,j]$ אינו **מצטמצם בהכרח**. --- ## בדיקת האפשרויות | אפשרות | תיאור | בעיה | |--------|-------|------| | 1 | `i = k-1` / `j = k+1` | **שגוי** — מרחיב את הטווח במקום לצמצם | | **2** | `i = k+1` / `j = k-1` | ✅ | | 3 | `if (a[k] <= x) i = k; else j = k;` | **שגוי** — עדיין עלולה ללולאה אינסופית כאשר `a[k]=x` | | 4 | שינוי תנאי ה-while ל-`a[k]==x` | **שגוי לחלוטין** — עוצר רק כשמצא, לא מסיים כשלא מצא | | 5 | הקוד תקין כמות שהוא | **שגוי** | --- ## התשובה הנכונה: אפשרות 2 ```java if (a[k] < x) i = k + 1; else j = k - 1; ``` **מדוע זה נכון?** - אם `a[k] < x`: כל האיברים עד $k$ קטנים מ-$x$ (המערך ממוין) ← בצדק נעביר $i = k+1$ - אם `a[k] >= x`: ← בצדק נעביר $j = k-1$ - בכל מקרה $j - i$ **מצטמצם בקפדנות** בכל איטרציה ← אין לולאה אינסופית שימו לב: אם `a[k] == x`, ה-`else` יריץ `j = k-1`, אך אז תנאי ה-`while` בודק `a[k] != x` — שהוא **שקר**, ולכן הלולאה מיד נעצרת וה-`k` עדיין מצביע על האיבר שנמצא ✓