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

נתונה מחרוזת המורכבת מהתווים 'a', 'b' ו-'c' בלבד. נתון כי התווים במחרוזת ממוינים לפי סדר האלף-בית. כמו כן במחרוזת ישנם יותר תווי 'c' (ממש) מאשר תווי 'a'. שימו לב כי בפרט, במחרוזת יש לפחות תו 'c' אחד. **סעיף א (12 נקודות):** כתבו שיטה סטטית **יעילה ככל הניתן** המקבלת כפרמטר מחרוזת תווים ממוינת כמתואר לעיל. השיטה צריכה להחזיר אינדקס של תו כלשהו **שאינו 'a'**. (שימו לב שבהכרח יש כזה כיוון שיש לפחות תו 'c' אחד). חתימת השיטה: ```java public static int findBC(String s) ``` **לדוגמה**: עבור המחרוזת "aaabbcccc" יוחזר ערך כלשהו בין 3 ל-8. (האינדקס של אחד מהתווים 'b' או 'c'. זכרו כי האינדקס של התו הראשון במחרוזת הוא 0). **הגבלות**: בכתיבת השיטה מותר להשתמש **אך ורק** בשיטת `charAt` שבמחלקה String. בפרט אסור להשתמש בשיטה `indexOf` ולא בשיטה `length`.

רמז: מכיוון שיש יותר תווי 'c' מתווי 'a', האינדקס האמצעי של המחרוזת בהכרח מכיל תו שאינו 'a'. השתמשו בחיפוש בינארי על מחרוזת ממוינת.

פתרון: מכיוון שהמחרוזת ממוינת ויש **יותר תווי 'c' מתווי 'a'**, האמצע של המחרוזת חייב להכיל תו שאינו 'a'. נשתמש בגישת **חיפוש בינארי**: נבדוק את התו באמצע - אם הוא אינו 'a' סיימנו, אחרת נחפש בחצי הימני. אך יש בעיה: אין לנו `length`. לכן תחילה נמצא את אורך המחרוזת על ידי ניסיון לגשת לתווים ב-**הכפלת אינדקס** עד שנקבל חריגה, ואז חיפוש בינארי על האורך. ```java public static int findBC(String s) { // מציאת גבול עליון לאורך int high = 1; try { while (true) { s.charAt(high); high *= 2; } } catch (StringIndexOutOfBoundsException e) { // high חורג מהמחרוזת } // חיפוש בינארי על האורך int lo = high / 2, hi = high; while (lo < hi) { int mid = (lo + hi) / 2; try { s.charAt(mid); lo = mid + 1; } catch (StringIndexOutOfBoundsException e) { hi = mid; } } int len = lo; // אורך המחרוזת // חיפוש בינארי על תו שאינו 'a' lo = 0; hi = len - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (s.charAt(mid) != 'a') return mid; else lo = mid + 1; } return -1; // לא יקרה לפי ההנחות } ``` **סיבוכיות זמן**: $O(\log n)$ כאשר $n$ אורך המחרוזת. **סיבוכיות מקום**: $O(1)$.