שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 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. אין צורך לשנות כלום. הקוד תקין.

רמז: הבעיה היא שכש-a[k] < x, i צריך להתקדם מעבר ל-k כדי שהלולאה תתכנס. חשבו מה קורה כש-i = k.

פתרון: **התשובה הנכונה היא 2:** `if (a[k] < x) i = k+1; else j = k-1;` **הסבר:** הבעיה בקוד המקורי היא שכאשר `a[k] < x`, הפקודה `i = k` לא מקדמת את `i` מספיק - אם `k = (i+j)/2 = i` (כשנותרו רק שני איברים), i לא ישתנה ותיווצר **לולאה אינסופית**. התיקון `i = k+1` מבטיח שהגבול התחתון תמיד מתקדם (כי אנחנו יודעים ש-a[k] קטן מ-x, אז אין צורך לבדוק אותו שוב). באופן דומה, `j = k-1` מבטיח שהגבול העליון תמיד קטן (כי a[k] >= x ואנחנו מחפשים ערך קטן יותר או שווה). **שימו לב:** לאחר התיקון, תנאי היציאה `a[k] != x && i < j` עדיין תקין, ויש לוודא שהבדיקה `a[k] == x` בסוף נכונה גם כן.