Ofer (guest) 29 Jan 2013 15:41
הי, אני תוהה בנוגע לפתרון של שאלה 3 במבחן של 2012א מועד ב'.
החלטתי שבמקום להסתבך אני פשוט אעשה דבר כזה:
1. בצע חיפוש בינארי רגיל. אם קיבלת True - אחלה.
2. אם קיבלת False - אז קח את כל ה-pivotים שבחרת בחיפוש הקודם, ותוריד אותם מהרשימה.
3. עכשיו בצע חיפוש בינארי נוסף על הרשימה. ותחזיר את התוצאה שקיבלת.
הרעיון פה הוא שאם בטעות בחרתי ב-pivot שלי את האיבר החריג ברשימה - אז הורדתי אותו לפני שהרצתי חיפוש בינארי בפעם השנייה.
ואם לא בחרתי בטעות ב-pivot שלי את האיבר החריג ברשימה ועדיין קיבלתי False בהרצה הראשונה - אז אין ספק שאני אקבל False בהרצה השניה, גם אם אני אעבור בטעות על האיבר החריג.
אם אני לא טועה - הסיבוכיות שלי היא כמו הסיבוכיות של חיפוש בינארי רגיל - zzz O(logn) zzz.
מה אתם אומרים? נשמע הגיוני?
(השאלה מופנית כמובן לכולם ולא רק למתרגלים ולמרצים)
