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

נתונה פונקציה `guess(x)` שמקבלת מספר שלם ומחזירה `">"` אם המספר הסודי גדול מ-$x$, `"<"` אם הוא קטן מ-$x$, ו-`"="` אם הוא שווה ל-$x$. א. (10 נקודות) כתבו פונקציה `find_secret(N1, N2)` שמוצאת את המספר הסודי, בהינתן שהוא נמצא בטווח $[N1, N2]$, באמצעות חיפוש בינארי. ב. (10 נקודות) כתבו פונקציה `find_secret2()` שמוצאת את המספר הסודי כאשר **אין** חסם עליון ידוע — המספר הסודי הוא מספר טבעי חיובי כלשהו.

רמז: בסעיף א' השתמשו בחיפוש בינארי רגיל. בסעיף ב', מצאו תחילה חסם עליון על ידי הכפלת הטווח (doubling) — התחילו עם $[1,2]$ והכפילו את שני הגבולות עד שהמספר הסודי נמצא בטווח, ואז הפעילו `find_secret`.

פתרון: **סעיף א':** ```python def find_secret(N1, N2): low = N1 high = N2 ans = "?" while ans != "=": mid = (low + high) // 2 ans = guess(mid) if ans == ">": low = mid + 1 else: high = mid - 1 return mid ``` **חיפוש בינארי** רגיל: בכל צעד שואלים על האמצע, ומצמצמים את הטווח בהתאם. סיבוכיות: $O(\log(N2 - N1))$. **סעיף ב':** ```python def find_secret2(): low = 1 high = 2 answer = guess(high) while answer == ">": low *= 2 high *= 2 answer = guess(high) if answer == "=": return high return find_secret(low, high) ``` **שלב 1 — מציאת חסם (doubling):** מתחילים עם $[1, 2]$ ומכפילים את שני הגבולות כל פעם. אחרי $k$ צעדים, $high = 2^{k+1}$. נעצרים כש-`guess(high)` מחזיר `"<"` או `"="`. אם המספר הסודי הוא $S$, צריך $O(\log S)$ צעדי הכפלה. **שלב 2 — חיפוש בינארי:** מפעילים `find_secret(low, high)` על הטווח שנמצא. סיבוכיות: $O(\log S)$ גם כאן. **סיבוכיות כוללת:** $O(\log S)$.